路径总和 III 为什么要用前缀和？和根到叶路径有什么区别？

简化版

路径总和 III 统计的是向下路径，不要求从根开始，也不要求到叶子结束。用 DFS + 前缀和哈希表，当前前缀和为 cur 时，之前出现过 cur - target 几次，就能贡献几条合法路径，时间 O(n)，空间 O(h) 到 O(n)。

详细版

根到当前节点的前缀和记为 cur。如果某个祖先前缀和是 prev，那么祖先之后到当前节点这段路径和就是 cur - prev；要让它等于 target，只要找 prev = cur - target。因此遍历时维护“当前路径上的前缀和次数表”。

int ans = 0;
Map<Long, Integer> count = new HashMap<>();

int pathSum(TreeNode root, int targetSum) {
    count.put(0L, 1);
    dfs(root, 0L, targetSum);
    return ans;
}

void dfs(TreeNode node, long cur, int target) {
    if (node == null) return;
    cur += node.val;
    ans += count.getOrDefault(cur - target, 0);
    count.put(cur, count.getOrDefault(cur, 0) + 1);
    dfs(node.left, cur, target);
    dfs(node.right, cur, target);
    count.put(cur, count.get(cur) - 1);
}

最后的减 1 是回溯，表示离开当前节点后，这个前缀和不再属于兄弟分支的路径。

完整版教学

一、这题和基础路径总和不是一类判定

基础路径总和通常要求“根到叶的一条完整路径”。路径总和 III 的要求更宽：路径只需要从某个节点向下走到某个后代节点，不要求从根开始，也不要求到叶子结束。这个变化让普通 DFS 不能只在叶子判断，也不能只维护一条从根开始的累计值。

合法路径可以是 5 -> 3，也可以是 -3 -> 11，它们都不是从整棵树根节点 10 开始。这就是为什么需要“任意祖先到当前节点”的差值关系。

二、前缀和把“任意起点”变成一次查表

在数组里，区间和可以用两个前缀和相减得到。树上也一样，只不过路径必须沿父子方向。假设根到当前节点的和是 cur，根到某个祖先节点之前的和是 prev，那么这段向下路径和就是 cur - prev。

cur - prev = target
prev = cur - target

所以到达一个节点时，不需要枚举所有祖先，只要查哈希表中 cur - target 出现了几次。出现几次，就说明有几条以当前节点为终点的合法路径。

三、为什么要先放一个前缀和 0

count[0] = 1 表示“还没经过任何节点时，前缀和为 0 出现过一次”。它处理的是路径刚好从根节点开始的情况。如果没有这个初始值，当 cur == target 时，查 cur - target = 0 会查不到，从根开始的路径就漏掉了。

当前前缀和 cur	target	需要的 prev	count[prev]	含义
8	8	0	1	根到当前节点是一条答案
18	8	10	1	某个祖先之后到当前节点是一条答案
18	8	10	2	有两个不同祖先位置可作为起点

这个初始化在数组前缀和题里也经常出现，树题只是多了回溯。

四、为什么哈希表必须随 DFS 回溯

哈希表里存的不是整棵树所有前缀和，而是“当前根到节点这条路径上的前缀和”。当 DFS 从左子树回到父节点再去右子树时，左子树节点的前缀和不能影响右子树。否则会把不在同一条向下路径上的两个节点拼起来，得到非法路径。

进入节点: count[cur]++
访问左子树
访问右子树
离开节点: count[cur]--

这个加一减一就是回溯的边界控制。它保证哈希表始终反映“从根到当前递归栈”的路径，而不是全局历史。

五、为什么用 long 更稳

节点值和路径长度都可能让累计和超过 int。例如 100000 个节点，每个节点值是 100000，路径和可到 10^10，已经大于 32 位整数范围。Java 里 int 最大约 2.1 * 10^9，溢出后会变成错误值，哈希表查找也会失真。

100000 * 100000 = 10000000000
Integer.MAX_VALUE = 2147483647

所以前缀和变量和哈希表 key 推荐用 long。哪怕题目数据较小，这个习惯也能避免面试官追问时暴露边界漏洞。

六、常见误区与追问

易错点：路径总和 III 的哈希表只属于“当前路径”，不是整棵树的全局频次表。

误区：路径必须从根开始。 这题允许从任意节点开始，只要方向向下即可。
误区：统计到叶子再判断。 路径可以在任意节点结束，每个节点都要作为终点统计一次。
误区：哈希表不回溯也能算。 不回溯会把不同分支的前缀和混在一起，产生非法路径。
误区：用 int 存前缀和足够。 大节点值或深树会溢出，实际代码建议用 long。
追问：为什么 count[0]=1？ 它表示空前缀，用来统计从根开始刚好等于目标值的路径。
追问：复杂度是多少？ 每个节点进出一次，时间 O(n)；空间取决于递归深度和路径上前缀和种类，最坏 O(n)。

七、加强记忆

这题的锚点是“树上的连续子数组和”。从根到当前节点形成一条线，任意向下路径就是这条线上的一个区间；区间和靠两个前缀和相减，起点数量靠哈希表计数。进入节点加前缀，离开节点减前缀，保证表里只保存当前路径，这样就把看似复杂的任意起点统计压成了一次 DFS。

简化版

详细版