建议先完成 Subarray Sum Equals K
-
我们可以观察到对于任意数组 sum(array[i, j]) = sum(array[0, j] - sum(array[0, i-1])
-
所以我们可以先创建一个 presum 数组，其中 presum[i] = sum(A[0,i])，例如 array = [1, 2, 3], 则 presum = [1, 3, 6]
-
根据 0，我们可以得到 sum(array[i, j]) = presum[j] - presum[i-1]
array[1:2] = 5 = presum[2] - presum[0] array[1:1] = 3 = presum[1] - presum[0]
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
target = 8
注意的是：这里的 path 不包括 由副节点同时连接左右子节点的情况，例如 [3, 5, 2] 或者 [5, 10, -3]，合法的 path 只能直接从父节点到子节点。
- brute force 的解法重复计算了节点和，例如在节点 3 的时候，计算了 10 + 5 + 3，不过 10 + 5 在计算 3 的父节点 5 的时候已经计算过。所以我们可以用一个 presum 列表保存从 root 节点到当前节点的 presum。
- 单独看 path [10, 5, 3, 3]，target 为 8，当计算到第三个节点 3 之前，presum 保存了 [10, 15]，到第三个节点的时候，新的 new_presum 值等于 18，在添加到 presum 数组之前我们可以遍历 presum 数组，看 new_presum - presum[i] 是否等于 target，在这个例子中，new_presum - presum[0] = target，最终结果加 1
- 我们可以使用hash table 来替代数组，看 new_presum - presum[i] 是否在 hash table 的键中，可以减少时间复杂度，同时我们用 hash table 的值来记录数量。
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> int:
if not root:
return 0
self.count = 0
self.dic = {0:1}
self.dfs(root, 0, sum)
return self.count
def dfs(self, node, pre, sum):
if node.val + pre - sum in self.dic:
self.count += self.dic[node.val + pre - sum]
if pre + node.val in self.dic:
self.dic[pre+node.val] += 1
else:
self.dic[pre+node.val] = 1
for n in (node.left, node.right):
if n:
self.dfs(n, pre+node.val, sum)
self.dic[pre+node.val] -= 1