Poison

437. Path Sum III

DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public int pathSum(TreeNode root, int targetSum) {
if (root == null) {
return 0;
}

// 从当前节点向下满足路径和的路径数量
int pathCount = dfs(root, targetSum);

// 因为题目要求路径不需要从根节点开始,即从任意节点开始均可,所以需要以下两行递归调用,注意对 pathSum 是递归调用
pathCount += pathSum(root.left, targetSum);
pathCount += pathSum(root.right, targetSum);

return pathCount;
}

private int dfs(TreeNode node, int targetSum) {
if (node == null) {
return 0;
}

int pathCount = 0;

if (node.val == targetSum) {
pathCount++;
}

pathCount += dfs(node.left, targetSum - node.val);
pathCount += dfs(node.right, targetSum - node.val);

return pathCount;
}
}
Backtracking + Prefix Sum
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public int pathSum(TreeNode root, int targetSum) {
Map<Long, Integer> prefixSumToCountMap = new HashMap<>();
prefixSumToCountMap.put(0L, 1);
return dfs(prefixSumToCountMap, root, 0, targetSum);
}

private int dfs(Map<Long, Integer> prefixSumToCountMap, TreeNode node, long prefixSum, int targetSum) {
if (node == null) {
return 0;
}

prefixSum += node.val;
int pathCount = prefixSumToCountMap.getOrDefault(prefixSum - targetSum, 0); // 注意此处是 prefixSum - targetSum, 不要搞反了
prefixSumToCountMap.put(prefixSum, prefixSumToCountMap.getOrDefault(prefixSum, 0) + 1);
pathCount += dfs(prefixSumToCountMap, node.left, prefixSum, targetSum);
pathCount += dfs(prefixSumToCountMap, node.right, prefixSum, targetSum);
prefixSumToCountMap.put(prefixSum, prefixSumToCountMap.get(prefixSum) - 1);
return pathCount;
}
}
Reference

437. Path Sum III
剑指 Offer II 050. 向下的路径节点之和