LeetCode 437. 路径总和 III
题目描述
题意分析
统计二叉树中节点值之和等于
targetSum的非空路径数量。路径必须沿父节点到子节点的方向连续向下，可以从任意节点开始，也可以在任意节点结束，不要求从根出发或到叶子结束；单个节点也可以构成路径。不能先向上再拐到另一分支，不同起止位置对应不同路径。节点值允许为负，所以当前和超过目标时不能停止搜索，后续的负值仍可能使路径和回到目标。
解法：DFS + 前缀和回溯
核心思路
[!blue]
固定路径的结束节点，只需知道它的祖先链上有多少个位置可以作为起点。令
prefix为从整棵树的根到当前节点的累加和，若起点前一个位置的前缀和为earlier，这条向下路径的和就是prefix - earlier。因此目标条件等价于earlier = prefix - targetSum。深度优先遍历时，用哈希表
count记录当前祖先链上各个前缀和的出现次数。不同祖先可能具有相同前缀和，它们代表不同的起点，所以需要保存次数，而不只是是否出现。到达当前节点并算出新prefix后，count[prefix - targetSum]就是以当前节点结束的合法路径数。初始放入
count[0] = 1，表示根节点之前的空前缀。它允许路径直接从根开始；这是起点之前的边界，不是一条单独计入答案的空路径。查询必须发生在登记当前前缀之前，否则目标为零时，当前前缀会与自身配对，错误地多算一条空路径。查询后将当前前缀次数加一，让子节点能够把它作为祖先边界，再递归左右子树。处理完两侧后，必须将当前前缀次数减一，撤销它对哈希表的贡献。这样返回父节点后，兄弟分支不会把当前节点误认为自己的祖先，表中所有正计数始终只对应当前路径。
回溯只减去本节点贡献的一次，不能直接删除同值前缀，因为其他祖先也可能留下相同的和。当前实现允许零计数键留在表中，它们查询结果为零，不会贡献路径。累加和可能超过 32 位范围，Java 使用
long，Go 使用int64。每条合法路径都有唯一的结束节点，并且会在访问该节点时由对应的起点前缀统计一次；汇总各节点的贡献，便得到全部路径数。
解题步骤
- 初始化前缀频次表
count[0] = 1，从根节点以初始前缀和零开始 DFS。- 若节点为空，返回零；否则将节点值加入
prefix。- 查询并记录
count[prefix - targetSum]，随后将count[prefix]加一。- 递归左右子树，把各自返回的路径数加入当前答案。
- 返回前将
count[prefix]减一，恢复进入当前节点之前的祖先前缀记录。
代码实现
class Solution {
public int pathSum(TreeNode root, int targetSum) {
Map<Long, Integer> count = new HashMap<>();
count.put(0L, 1);
return dfs(root, 0L, targetSum, count);
}
private int dfs(TreeNode node, long prefix, int target, Map<Long, Integer> count) {
if (node == null) {
return 0;
}
prefix += node.val;
// 先查祖先前缀，再加入当前前缀，避免把空路径计入。
int answer = count.getOrDefault(prefix - target, 0);
count.put(prefix, count.getOrDefault(prefix, 0) + 1);
answer += dfs(node.left, prefix, target, count);
answer += dfs(node.right, prefix, target, count);
// 离开当前节点时仅撤销一次计数，其他同值祖先记录仍保留。
count.put(prefix, count.get(prefix) - 1);
return answer;
}
}
func pathSum(root *TreeNode, targetSum int) int {
count := map[int64]int{0: 1}
var dfs func(*TreeNode, int64) int
dfs = func(node *TreeNode, prefix int64) int {
if node == nil {
return 0
}
prefix += int64(node.Val)
// 先查祖先前缀，再加入当前前缀，避免把空路径计入。
answer := count[prefix-int64(targetSum)]
count[prefix]++
answer += dfs(node.Left, prefix)
answer += dfs(node.Right, prefix)
// 离开当前节点时仅撤销一次计数，其他同值祖先记录仍保留。
count[prefix]--
return answer
}
return dfs(root, 0)
}
复杂度分析
- 时间复杂度：期望 $O(n)$，每个节点只访问一次，每次做常量次哈希查询和计数更新。
- 空间复杂度：$O(n)$。当前代码保留零计数键，哈希表最坏可存下整棵树产生的
n种前缀；递归栈深为树高h，最坏也为 $O(n)$。
关键点总结
[!green]
- 固定路径终点，用前缀差把枚举起点转换成一次频次查询。
- 哈希表中有效的正计数只属于当前祖先链，递归返回时的撤销是限制路径方向的关键。
- 同值前缀的次数表示多个合法起点，不能用集合代替，也不能回溯时整体删除。
- 每个节点遵循先查、再登记、递归、撤销的顺序。
易错点总结
[!yellow]
- 忘记回溯减一，兄弟分支会把已经离开的节点当作祖先，统计出不存在的跨分支路径。
- 先登记当前前缀再查询，会在目标为零时把当前前缀与自身组成的空路径计入。
- 直接删除前缀键，会一并删除其他同值祖先的贡献；只能撤销当前节点增加的一次。
- 漏掉初始空前缀，会少算所有从根开始且和为目标的路径。
- 只使用 32 位累加和或根据当前和大于目标剪枝，都会忽略题目允许的数值范围与负数情况。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 560. 和为 K 的子数组 | 中等 | 把数组的前缀和频次计数推广到树上，离开分支必须撤销当前前缀。 |
| 113. 路径总和 II | 中等 | 原题只枚举根到叶路径，本题允许任意祖先作为起点且只统计数量。 |
| 325. 和等于 k 的最长子数组长度 | 中等 | 前缀和配合哈希表查找所需历史前缀；本题沿树路径维护前缀次数并回溯恢复，该题存最早前缀下标以最大化长度。 |
| 930. 和相同的二元子数组 | 中等 | 前缀和配合哈希表查找所需历史前缀；本题沿树路径维护前缀次数并回溯恢复，该题二进制数组上统计目标和。 |
| 1248. 统计「优美子数组」 | 中等 | 前缀和配合哈希表查找所需历史前缀；本题沿树路径维护前缀次数并回溯恢复，该题把奇数映射为 1 后统计精确数量。 |
| 补充题 181. 二叉树中和为目标值的所有向下路径 | 中等 | 都在 DFS 中维护当前祖先链的前缀和；本题累计路径数，补充题还还原具体路径。 |
| 112. 路径总和 | 简单 | 路径总和系列。I 只检查根到叶的目标和路径；III 允许任意祖先到后代的路径，并用前缀和计数。 |