Path Sum

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.

Java代码

public boolean hasPathSum(TreeNode root, int sum) {
    if(root==null) return false;
    if(root.val == sum && root.left==null && root.right==null) return true;

    return hasPathSum(root.left, sum-root.val) || hasPathSum(root.right, sum-root.val);
}

Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

public void pathSumInner(TreeNode root, int sum, List<Integer>path,
   List<List<Integer>> result) {
    path.add(root.val);
    if(root.left == null && root.right == null)
        if(sum == root.val) result.add(new ArrayList<Integer>(path));
    if(root.left!=null) pathSumInner(root.left, sum-root.val, path, result);
    if(root.right!=null)pathSumInner(root.right, sum-root.val, path, result);
    path.remove(path.size()-1);
}

public List<List<Integer>> pathSum(TreeNode root, int sum) {
    List<List<Integer>> resultList = new ArrayList<List<Integer>>();
    if(root==null) return resultList;
    List<Integer> currentPath = new ArrayList<Integer>();
    pathSumInner(root, sum, currentPath, resultList);
    return resultList;
}