437. Path Sum III

Problem:

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

Analysis:
4/23/2018 update:
用presum的方法更好啊，递归套递归，把自己套晕了。
This problem is underrated, can category to medium.

Solution 1 (Top down recursion) :
The path sum of root = pathSumFrom(root) + pathSum(root.left) + pathSum(root.right).
When implementing pathSumFrom,  when found root.val == sum, don't stop. Cuz' there are cases when the following path's sum would be 0.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int pathSum(TreeNode root, int sum) {
        if (root == null) return 0;
        return pathSumFrom(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    }
    
    private int pathSumFrom(TreeNode root, int sum) {
        int res = 0;
        if (root == null) return 0;
        if (root.val == sum) res++;
        return res + pathSumFrom(root.left, sum - root.val) + pathSumFrom(root.right, sum - root.val);
    }
}

Solution 2 (Prefix sum + DFS): 
Perfect scenario to go with preSum. Cut each pah top down as array, it's just get number of subarray sum problem. Note that preSum can be duplicate so that mean multiple sub path under one path.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int pathSum(TreeNode root, int sum) {
        if (root == null) return 0;
        Map<Integer, Integer> preSum = new HashMap<>();
        preSum.put(0, 1);
        return helper(root, sum, 0, preSum);
    }
    
    private int helper(TreeNode root, int target, int sum, Map<Integer, Integer> preSum) {
        if (root == null) 
            return 0;
        int curSum = sum + root.val;
        int res = preSum.getOrDefault(curSum - target, 0);
        // add curSum to preSum
        preSum.put(curSum, preSum.getOrDefault(curSum, 0) + 1);
        res += helper(root.left, target, curSum, preSum) + helper(root.right, target, curSum, preSum);
        preSum.put(curSum, preSum.get(curSum) - 1);
        return res;
    }
}