1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Solution:
prefixsum_count = dict()
def dfs(self, root, prefixsum_count, target_sum, cur_sum):
if not root:
return 0
res = 0
cur_sum += root.val
res += prefixsum_count.get(cur_sum - target_sum, 0)
prefixsum_count[cur_sum] = prefixsum_count.get(cur_sum, 0) + 1
res += self.dfs(root.left, prefixsum_count, target_sum, cur_sum)
res += self.dfs(root.right, prefixsum_count, target_sum, cur_sum)
prefixsum_count[cur_sum] -= 1
return res
def pathSum(self, root: TreeNode, targetSum: int) -> int:
if not root:
return 0
prefixsum_count = dict()
prefixsum_count[0] = 1
return self.dfs(root, prefixsum_count, targetSum, 0)
|