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

The trick in this problem is to fully understand it, that is, since the path may starts from everywhere:
every node can be the beginning root of the path.
Therefore, be careful when writing the recursion, we should add in the left and right children of the root.
This is also a DFS solution, the time cost is O(n^2) for worst case (no branching) and O(nlogn) for balanced tree.

/**
 * 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 helper(root,sum) + pathSum(root.left,sum) + pathSum(root.right,sum);
        // every node can start the path, 
        // so recursion should also start from the left and right children of root
    }

    public int helper(TreeNode root,int sum){
        if(root==null) return 0;
        int res = helper(root.left, sum-root.val)+helper(root.right, sum-root.val);
        return (root.val==sum)?++res:res;
        // if the root.val equals sum, the root node itself is a valid path
    }
}