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 andsum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
return true, as there exist a root-to-leaf path5->4->11->2which sum is 22.
代码 1
import java.util.ArrayList;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> arr=new ArrayList<Integer>();
public boolean hasPathSum(TreeNode root, int sum) {
if(root==null)return false;
isPath(root,0,sum);
if(result.isEmpty())return false;
else return true;
}
private void isPath(TreeNode root, int sum, int target) {
if(root==null)return;
else{
sum+=root.val;
arr.add(root.val);
if(root.left==null&&root.right==null&&sum==target){
result.add(new ArrayList<Integer>(arr));
}
isPath(root.left, sum, target);
isPath(root.right, sum, target);
arr.remove(arr.size()-1);
sum-=root.val;
}
}
}
代码二：
import java.util.ArrayList;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
return hasPathSumHelper(root, sum);
}
private boolean hasPathSumHelper(TreeNode root, int sum) {
// TODO Auto-generated method stub
if(root==null)return false;
if(root.left==null&&root.right==null&&sum==root.val)return true;
return hasPathSumHelper(root.left, sum-root.val)||hasPathSumHelper(root.right, sum-root.val);
}
}