動機
原來是prefix sum的靈壓!!
Problem
Given the root
of a binary tree and an integer targetSum
, return the number of paths where the sum of the values along the path equals targetSum
.
The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).
Example 1:
Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8Output: 3Explanation: The paths that sum to 8 are shown.
Example 2:
Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22Output: 3
Constraints:
- The number of nodes in the tree is in the range
[0, 1000]
. -109 <= Node.val <= 109
-1000 <= targetSum <= 1000
Sol
最簡單一個走一個找
class Solution:
def pathSum(self, root: TreeNode, val: int) -> int:
def count(r,acc):
if not r:
return 0
elif acc+r.val == val:
ret = 1
else:
ret = 0
ret += count(r.left,acc+r.val)+count(r.right,acc+r.val)
return ret
def dfs(r):
if not r:
return 0
else:
return count(r,0)+dfs(r.left)+dfs(r.right)
return dfs(root)
或是善用prefix sum,不過這是tree,所以要在遞迴離開之前要把原本的sum註銷掉
class Solution:
def pathSum(self, root: TreeNode, targetSum: int) -> int:
sums = defaultdict(int)
sums[0] = 1
ret = 0
def dfs(r,cnt):
nonlocal ret
if not r:
return
else:
cnt += r.val
ret += sums[cnt - targetSum] # targetSum = sums[a:b] = sums[b](cnt) - sums[a]
sums[cnt] += 1
dfs(r.left, cnt)
dfs(r.right, cnt)
sums[cnt] -= 1 # 離開之前要把原本的sum註銷掉
dfs(root,0)
return ret