作为java工程师,用迭代法写一个算法求二叉树路径和,如果求出指定和,则返回。并写出详细注释
时间: 2024-05-15 11:19:45 浏览: 35
二叉树的创建以及路径查找
```java
/**
* 二叉树节点定义
*/
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
/**
* 二叉树路径和迭代解法
*/
public class BinaryTreePathSum {
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) {
return false;
}
// 创建两个栈,一个存储节点,一个存储到该节点的路径和
Stack<TreeNode> nodeStack = new Stack<>();
Stack<Integer> sumStack = new Stack<>();
nodeStack.push(root);
sumStack.push(root.val);
while (!nodeStack.isEmpty()) {
TreeNode node = nodeStack.pop();
int pathSum = sumStack.pop();
// 如果该节点是叶子节点,并且到该节点的路径和等于指定和,则返回true
if (node.left == null && node.right == null && pathSum == sum) {
return true;
}
// 如果该节点有左子树,则将左子节点和到该节点的路径和入栈
if (node.left != null) {
nodeStack.push(node.left);
sumStack.push(pathSum + node.left.val);
}
// 如果该节点有右子树,则将右子节点和到该节点的路径和入栈
if (node.right != null) {
nodeStack.push(node.right);
sumStack.push(pathSum + node.right.val);
}
}
return false;
}
}
```
阅读全文