正文
Path Sum leetcode java
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
题目 ：
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.
题解 ：
还是对树的操作，递归的解法：
1 public boolean hasPathSum(TreeNode root, int sum) {
2 if(root == null)
3 return false;
4
5 sum -= root.val;
6 if(root.left == null && root.right==null)
7 return sum == 0;
8 else
9 return hasPathSum(root.left,sum) || hasPathSum(root.right,sum);
}
非递归的解法（Reference：http://www.programcreek.com/2013/01/leetcode-path-sum/）：
1 public boolean hasPathSum(TreeNode root, int sum) {
2 if(root == null) return false;
3
4 LinkedList<TreeNode> nodes = new LinkedList<TreeNode>();
5 LinkedList<Integer> values = new LinkedList<Integer>();
6
7 nodes.add(root);
8 values.add(root.val);
9
while(!nodes.isEmpty()){
TreeNode curr = nodes.poll();
int sumValue = values.poll();
if(curr.left == null && curr.right == null && sumValue==sum){
return true;
}
if(curr.left != null){
nodes.add(curr.left);
values.add(sumValue+curr.left.val);
}
if(curr.right != null){
nodes.add(curr.right);
values.add(sumValue+curr.right.val);
}
}
return false;
}
