LeetCode LCR 050. 路径总和 III
题目描述
题意分析
统计节点值之和等于
targetSum的非空路径数。路径只能从父节点向子节点延伸，起点不必是根，终点也不必是叶子。节点值可以为负数，路径和不具有单调性，不能因当前和超过目标而停止搜索。
解法：前缀和与回溯计数
核心思路
[!blue]
固定当前节点作为终点，所有合法路径都是根到当前节点这条链的一段后缀。设根到当前节点的累计和为
s，某个祖先处的累计和为p，那么从该祖先的下一个节点走到当前节点，路径和就是s-p。要等于目标，只需找出祖先链上有多少个p=s-targetSum。用
cnt记录当前祖先链中每种前缀和出现的次数。同一前缀和值可能出现在多个祖先处，每个位置都对应不同的路径起点，因此需要频次而非仅记录是否存在。预置cnt[0]=1，表示根之前的空前缀，使从根开始的路径也能用相减公式统计。到达当前节点后，先累加节点值得到
s，再查询cnt[s-targetSum]。此时表中只应有当前节点之前的祖先前缀，查到的都是非空路径。随后将s登记到表中，供左右子树作为祖先前缀使用。两侧递归结束后，把
cnt[s]减一，恢复进入当前节点前的状态。这样一条分支中的节点不会被另一分支误当成祖先。每条合法路径在自己的终点被统计一次，对当前节点与左右子树的计数相加，就得到总数。
解题步骤
- 初始化空前缀计数，从累计和 0 开始递归；空节点返回 0。
- 加上当前节点值，用
cnt[s-targetSum]得到以当前节点为终点的路径数。- 执行
cnt[s]++，递归左右孩子，并累加它们的返回值。- 执行
cnt[s]--撤销当前前缀，再返回当前子树内统计到的路径数。查询必须早于登记：当目标为 0 时，若先登记当前前缀，就会把当前前缀与自身相减，当成一条实际上不含任何节点的空路径。单个零节点的合法路径应由它之前的祖先前缀来计数。累计和可能超过 32 位，Java 用
long，Go 显式使用int64。
代码实现
class Solution {
private Map<Long, Integer> cnt = new HashMap<>();
private int targetSum;
public int pathSum(TreeNode root, int targetSum) {
cnt.put(0L, 1);
this.targetSum = targetSum;
return dfs(root, 0);
}
private int dfs(TreeNode node, long s) {
if (node == null) {
return 0;
}
s += node.val;
int answer = cnt.getOrDefault(s - targetSum, 0);
cnt.merge(s, 1, Integer::sum);
answer += dfs(node.left, s);
answer += dfs(node.right, s);
cnt.merge(s, -1, Integer::sum);
return answer;
}
}
func pathSum(root *TreeNode, targetSum int) int {
cnt := map[int64]int{0: 1}
var dfs func(*TreeNode, int64) int
dfs = func(node *TreeNode, s int64) int {
if node == nil {
return 0
}
s += int64(node.Val)
answer := cnt[s-int64(targetSum)]
cnt[s]++
answer += dfs(node.Left, s) + dfs(node.Right, s)
cnt[s]--
return answer
}
return dfs(root, 0)
}
复杂度分析
- 时间复杂度：期望 $O(n)$，每个节点只查询和更新哈希计数常数次。
- 空间复杂度：$O(n)$。当前实现不删除计数归零的键，一次遍历最多留下 $n$ 个不同节点前缀；递归栈为 $O(h)$。非零计数只对应当前链，不意味着映射实际只占 $O(h)$ 空间。
关键点总结
[!green]
- 查询的是当前祖先链上的前缀频次，不能使用整棵树已经访问过的所有前缀。
- 空前缀让从根开始的路径参与计数；先查询再登记排除空路径。
- 进入时登记、离开时撤销，左右子树才能安全共用一张表。
易错点总结
[!yellow]
- 预置空前缀 0 一次，先查询当前和减 target，再登记当前前缀。
- 两侧递归完成后撤销当前前缀，让非零计数只描述当前祖先路径。
- 累计和使用 64 位，节点值可有正负，不能因当前和超过目标就剪枝。
- 路径只能向下，不允许从左子树经过父亲转到右子树。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 560. 和为 K 的子数组 | 中等 | 把数组的前缀和频次计数推广到树上，离开分支必须撤销当前前缀。 |
| 113. 路径总和 II | 中等 | 原题只枚举根到叶路径，本题允许任意祖先作为起点且只统计数量。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！