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 1Return 3. The paths that sum to 8 are:1. 5 -> 32. 5 -> 2 -> 13. -3 -> 11 这个题目的思路就是类似于, 只不过我们不需要一定是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
1 class Solution:2 def pathSum3(self, root, target):3 def rootSum(root, target): # helper function to get number of paths from root -> any child node s.t sum == target4 if not root: return 05 d = target - root.val6 temp = 1 if d == 0 else 07 return temp + rootSum(root.left, d) + rootSum(root.right, d)8 if not root: return 09 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