Path Sum

题目地址：
https://leetcode.com/problems/path-sum/description/

题目：

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.

解题思路：
这道题就是用top-down的dfs来解决。

代码：

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

Follow up:
如果可以保证有root to leaf的path，现在要找出所有的path并且返回。这也是用top-down的方法。

public List<List<Integer>> pathSum(TreeNode root, int sum) {
    List<List<Integer>> rst = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    helper(root, sum, rst, list);
    return rst;
}

private void helper(TreeNode root, int sum, List<List<Integer>> rst, List<Integer> list) {
    if(root == null){
        return;
    }
    sum -= root.val;
    list.add(root.val);
    if(root.left == null && root.right == null){
        if(sum == 0){
            rst.add(list);
        }
        return;
    }
    helper(root.left, sum, rst, new ArrayList<>(list));
    helper(root.right, sum, rst, new ArrayList<>(list));
}

Follow up:
如果可以是任意的从上往下的path。这个时候也是用top-down的dfs，然后将自己和两个子树的结果加起来就是。reference：https://discuss.leetcode.com/topic/64388/simple-ac-java-solution-dfs

public int pathSum(TreeNode root, int sum) {
    if(root == null){
        return 0;
    }
    return find(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
}

private int find(TreeNode root, int sum) {
    if(root == null){
        return 0;
    }
    int rst = 0;
    if(sum == root.val){
        rst++;
    }
    rst += find(root.left, sum - root.val);
    rst += find(root.right, sum - root.val);
    return rst;
}