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

这个题目的思路就是类似于[LeetCode] 113. Path Sum II, 只不过我们不需要一定是leaf再判断, 同时recursive root.left and root.right, 最后返回总的个数即可.

1. Constraints
1) empty => 0

2. IDeas

DFS     T: O(n^2)  worst cases, when like linked lists
        T: O(nlgn)  best cases, when balanced tree   because height = lgn

1) edge case, if not root: return 0
2) create a helper function, get number of paths from root -> any child node s.t sum(path) == target
3) return helper(root) and recursively call root.left and root.right

3. Code

 class Solution:

     def pathSum3(self, root, target):

         def rootSum(root, target):  # helper function to get number of paths from root -> any child node s.t sum == target

             if not root: return 0

             d = target - root.val

             temp = 1 if d == 0 else 0

             return temp + rootSum(root.left, d) + rootSum(root.right, d)

         if not root: return 0

         return rootSum(root, target) + self.pathSum3(root.left, target) + self.pathSum3(root.right, target)

4. Test cases

1) empty

2) 1, 1

3)

1

     /  \

    1   1

               target = 1
4)

target = 8

      10

     /  \

    5   -3

   / \    \

  3   2   11

 / \   \

3  -2   1