路径总和 III

最直接的想法：以每个节点为起点，再往下走一遍累加，看能不能凑到 target。一共 n 个起点、每条往下又是 O(n)，最坏 O(n²)。能过，但慢，而且重复加了一遍又一遍。

换个角度。记 cur 是「从根一路加到当前节点」的前缀和。如果这条根到当前的路径上，某个更早的位置前缀和等于 cur−target，那么从那之后到当前这一段，和就正好是 target。于是问题变成：cur−target 在表里出现过几次。

我们维护一张哈希表，键是前缀和，值是它在「当前这条根到节点的路径」上出现了几次。一开始放一个 0 出现 1 次，代表「空前缀」，这样从根直接出发、整段正好等于 target 的路径也能被数到。

起点：根 10：进入根节点 10。前缀和 cur 变成 10，要找 10−8=2，表里没有 2，不命中。然后把 10 记进表：现在表是 0 一次、10 一次。

往左到 5：走到左孩子 5，前缀和累加到 15，要找 7。表里只有 0、10，没有 7，不命中。把 15 记进表。

再往左到 3 —— 第一次命中：走到节点 3，前缀和到 18，要找 18−8=10。表里 10 出现过 1 次！这意味着从「前缀和为 10 的位置」之后到现在，正好和为 8，也就是路径 5→3。答案加 1。

灵魂帧 · 命中那一刻在算什么：把这一刻拆开看：我不是去枚举起点，而是反过来问——之前哪个前缀和等于 18 减 8。表里 10 对应 1，就说明有 1 条以当前节点结尾、和为 8 的路径。这一步把 O(n) 的回溯枚举压成了一次 O(1) 查表，是全题的灵魂。

继续往下到 3 的左孩子 3：再往下到这个 3，前缀和 21，要找 13，表里没有，不命中。这条分支到此结束，接下来要往回走了。

回溯：离开节点，撤销它的前缀：这是和数组前缀和最不一样的地方：树会分叉。离开一个节点往回走时，必须把它贡献的前缀次数减回去。否则等会儿走到兄弟分支，会误把「不在这条路径上」的 21 当成可用前缀，凭空多数路径。

走到 5 的右支 2→1 —— 第二次命中：回到 5，改走右边的 2 再到 1，前缀和又是 18，找 10 再次命中。这条路径是 5→2→1，同样和为 8。答案到 2。注意刚才撤销了 21，表是干净的，没有串味。

切到右子树 -3→11 —— 第三次命中：左子树彻底退完后，表又回到只剩根的状态，走右子树 -3 再到 11。10 减 3 加 11，前缀和还是 18，找 10 第三次命中，路径 -3→11。答案到 3。

DFS 结束，返回答案：所有节点进出 DFS 一遍，三次命中标成绿色。整棵树只走了一遍，答案是 3。

一句话本质：不要枚举起点，而是用「当前前缀 cur 减去 target」去表里查历史前缀出现了几次。数组前缀和搬到树上，唯一多出来的就是「回溯撤销」。

面试追问：这三问串起了「迁移来源、边界初始化、工程细节」，把动画里的状态定义讲成自己的话即可。

迁移阶梯：把这题练到能脱稿复述后，去同类题里迁移：先复用「前缀和 → 次数」的状态定义，再按新题调整边界。也可以让 AI 助教小欧出一道变体、或进通关训练里实战一遍。

边界三连：极端先看空树、最小规模，再专门挑一个含负数的小例子——负数最容易暴露「只想着正数累加」「忘了 0 初始化」这类 bug。