Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
For example:Given the below binary tree and
sum = 22
,5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1
return true, as there exist a root-to-leaf path
5->4->11->2
which sum is 22.
Solution 1: Recursive DFS
public class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
return dfs(root,0,sum);
}
private boolean dfs(TreeNode x, int num, int sum) {
if (x==null) return false;
if (x.left==null && x.right==null) {
if (num+x.val==sum) return true;
else return false;
}
return dfs(x.left,num+x.val,sum) || dfs(x.right,num+x.val,sum);
}
}
Solution 2: Iterative DFS.
public class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
Deque<TreeNode> s1=new LinkedList<>();
Deque<Integer> s2=new LinkedList<>();
TreeNode x=root;
int num=0;
while (x!=null || !s1.isEmpty()) {
if (x!=null) {
num+=x.val;
s1.push(x);
s2.push(num);
x=x.left;
}
else {
x=s1.pop();
num=s2.pop();
if (x.left==null && x.right==null && num==sum) return true;
x=x.right;
}
}
return false;
}
}
没有评论:
发表评论