二叉树路径总和 III：前缀和+哈希表把暴力DFS优化到O(n)

LeetCode 437. 路径总和 III 是我刷题笔记里单独占了一页的一道题。原因很简单：二叉树路径求和这个系列里，前两题都是"根到叶子"的固定玩法，到了第三题起点和终点全都不固定，网上不少题解一上来就甩前缀和加哈希表，代码就十来行，但没看懂的人照抄一遍下次还是不会。这篇笔记我用自己的完整思考链来写——从暴力 DFS 怎么想、为什么慢，到前缀和怎么把问题变成一次查表，再到实际提交时踩过的坑，最后把它和同一家族的题目串起来。如果你最近也在刷 leetcode 热门 100 题，或者想系统补一下"前缀和"这个套路，这篇应该能帮上忙。

1. 先把题目读透：437 和 112、113 不是同一道题

1.1 题目到底在问什么

用大白话翻译一遍题目：给一棵二叉树和一个整数 targetSum，数一数树里一共有多少条"从任意节点出发、沿着父到子的方向、长度任意"的路径，让路径节点值之和等于 targetSum。路径不用从根开始，也不用在叶子结束。

官方示例长这样：

10 / \ 5 -3 / \ \ 3 2 11 / \ \ 3 -2 1

targetSum = 8，答案是 3，三条路径分别是：5 → 3、5 → 2 → 1、-3 → 11。注意第一条路径的起点是 5 而不是根，终点是 3 而 3 下面还有孩子；第三条路径的起点是负值节点。-3 加 11 正好等于 8，这种"负数开头"的路径在前两题里根本不会出现，因为前两题的起点锁死在根上。

数据范围也要先记清楚：节点数最多 1000，节点值在 [-1000, 1000]，targetSum 也在 [-1000, 1000]。这意味着路径上可能出现负数，前缀和不是单调递增的，后面讲优化的时候会反复用到这一点。

1.2 三兄弟放一起对比，差异一目了然

LeetCode 里路径总和有三道题，很多刷题新手容易混，先放个对比表：

112 和 113 之所以简单，是因为起点锁死在根，你只要在递归时把 target 减掉当前节点值往下传，走到叶子判断剩没剩 0 就行。437 把起点和终点都放开了，一套"根到叶子"的递归直接失效——你不能假设每条路径都从当前递归入口开始，也不能假设到达叶子才能结算。这个"任意到任意"是质变，不是量变。

还有一个高频思维陷阱：以为"当前和一旦超过 targetSum 就可以剪枝"。因为有负数，路径和可以先到 9 再跌回 8，剪枝会误杀正确答案。这个陷阱在暴力解法里最明显，所以下面先上暴力。

2. 暴力解法先上手：每个节点都当一次路径起点

2.1 双层递归的思路拆解

暴力思路其实很直白：路径必须向下走，那我就枚举"起点"。树里每个节点都有资格当起点，固定起点之后，问题退化成"从这个节点出发往下走，能走出几条和为 targetSum 的下降路径"——这不就是熟悉的递归吗？

所以代码是两层递归嵌套：

class Solution: def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int: if not root: return 0 # 以 root 为起点能凑出的路径数 + 不以 root 为起点的路径数 return ( self._count_from(root, targetSum) + self.pathSum(root.left, targetSum) + self.pathSum(root.right, targetSum) ) def _count_from(self, node: Optional[TreeNode], remain: int) -> int: if not node: return 0 # 当前节点自己就是一条合法路径的终点 cnt = 1 if node.val == remain else 0 # 路径还可以继续往下延伸 cnt += self._count_from(node.left, remain - node.val) cnt += self._count_from(node.right, remain - node.val) return cnt

注意 _count_from 里用了一个"剩余值"参数，每次往下走就把当前节点值减掉。这样写的好处是语义清楚：remain 表示"从这一个起点走到当前节点，还差多少和"。当 remain 恰好等于当前节点值时，说明当前节点可以作为一条路径的终点，计 1 条；同时你还要继续递归左右孩子，因为路径可以继续延伸。外层 pathSum 负责让每个节点都当一次起点，里层 _count_from 负责从固定起点向下统计，两层各司其职，边界情况也不会漏。

2.2 复杂度分析和"为什么能 AC 但别止步"

外层每个节点都要执行一次以自己为起点的向下遍历。最坏情况是树退化成一条链，第一个节点要往下扫 n 个节点，第二个扫 n-1 个……总操作量是 1+2+...+n，O(n²) 没跑。如果是平衡二叉树，每一层节点往下扫的深度递减，总操作量接近 n log n，但题目给的测试里链状树并不少见，所以必须按最坏情况算。空间上递归栈最深是 O(n)。

LeetCode 原题节点数上限是 1000，所以暴力其实能通过，很多题解区评论也会说"直接过"。这没问题，但我建议把它当成理解的起点，而不是交上去的终点，理由有两个：第一，面试官几乎必然会追问"数据量放大到 10^5 怎么办"，O(n²) 在这种追问下直接被抬走；第二，暴力的双层递归是前缀和解法的天然对照实验——你先看到暴力在哪个环节重复计算，才能理解前缀和解法到底优化掉了什么。重复计算的正是"每条路径的起点都要被扫一遍"这件事，下面就来解决它。

3. 前缀和 + 哈希表：把"逐对枚举"换成"一次查表"

3.1 关键公式：任意一条下降路径的和 = 两个前缀和之差

定义 prefix(node) 为从根走到 node 时，路径上节点值累加得到的总和。那么对于任意一条从 a 到 b 的下降路径（b 在 a 的子树里），它的路径和可以写成：

路径和 = prefix(b) - 路径起点之前停住的那个前缀和

换句话说，路径和等于"当前节点的前缀和"减去"路径起点之前的前缀和"。打个比方：前缀和就像每走一步记一次账本累计值，你要查某一段花了多少钱，只要拿当前累计值减去那一小段开始之前的累计值就行，中间不用重新数。如果路径起点就是根节点，那"起点之前的前缀和"就是初始的 0，对应后面要讲的 {0: 1}。

于是核心问题变成：DFS 走到节点 b、手里拿着当前前缀和 cur 时，在这条从根到 b 的路径上，历史上出现过几次前缀和等于 cur - targetSum？出现一次，就说明有一个起点能和 b 组成一条合法路径；出现 k 次，就有 k 条。所以我们要的是一个"前缀和 -> 出现次数"的计数哈希表，而不是简单的存在性集合。

3.2 为什么要先放一个 {0: 1}

初始化放进 {0: 1}，表示"前缀和为 0 的情况出现过一次"。这个 0 代表路径从根节点开始的选项——根节点之前的空前缀和就是 0。如果没有它，所有起点在根的路径（比如根到某个子孙节点刚好等于 targetSum 的情况）都会被漏掉。后面第 5 节我会用具体例子演示漏掉它的后果，这里先记住：这一行是必写的。

3.3 不画图，用官方示例走一遍关键步骤

还是上面那棵树，targetSum = 8，我挑有信息量的关键节点说：

• 根节点 10：cur = 10，查 10-8=2，map 里没有，ans 还是 0。把 10 放进 map。
• 节点 5：cur = 15，查 15-8=7，没有。map 里 15 入表。
• 节点 3（5 的左孩子）：cur = 18，查 18-8=10，map 里有 10（根节点的前缀），命中 1 次。ans 变 1。这次命中对应路径 5 → 3：从根节点之后截断起点，起点是 5，和正好 5+3=8。
• 继续走到 3 的左右孩子、回溯，回到节点 5 后去右子树：节点 2 的 cur = 17，查 17-8=9，没有；节点 1 的 cur = 18，查 18-8=10，map 里还是有 10，再命中 1 次。ans 变 2，对应路径 5 → 2 → 1。
• 回到根，进右子树：节点 -3 的 cur = 7，查 7-8=-1，没有；节点 11 的 cur = 18，又查 18-8=10，map 里还是有根的前缀 10，再命中 1 次。ans 变 3，对应路径 -3 → 11。

三次命中查的是同一个前缀和 10，对应的起点分别是 5、5、-3，共同点是"从根之后截断，剩下那段刚好凑出 8"。整个过程每个节点只访问一次，每次查表是 O(1)，这就是 O(n) 的由来。

3.4 回溯的本质：map 只保留当前这条根到节点的路径

这里有个最容易写错也最关键的动作：每个节点递归完左右子树之后，必须把自己这个前缀和的计数减回去（prefix[cur] -= 1）。原因是 map 描述的是"当前正在走的这条根到节点路径上前缀和的分布"，不是整棵树的前缀和分布。节点一旦回溯，它就不再位于当前路径上，它的前缀计数必须消失，否则左右子树之间会"串线"。

串线的后果具体表现为：把左子树某个节点当前缀起点、右子树某个节点当终点的"伪路径"也算进去。真实路径只能一路向下，不能从左边上去再拐到右边，但残留的前缀和会让这种非法组合在数值上"恰好等于 targetSum"，从而混进答案。我在第 5 节会给一个能跑出来的错误例子。

4. 最终代码与回溯细节：就那几行，但每一行都有讲究

4.1 Python 参考实现

class Solution: def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int: self.ans = 0 prefix = {0: 1} # 前缀和 -> 出现次数，{0:1} 代表"路径从根开始" def dfs(node: Optional[TreeNode], cur: int) -> None: if not node: return cur += node.val # 当前节点作为路径终点：前缀和 cur-targetSum 出现几次就有几条 self.ans += prefix.get(cur - targetSum, 0) # 前缀和入表，再去遍历子树 prefix[cur] = prefix.get(cur, 0) + 1 dfs(node.left, cur) dfs(node.right, cur) # 回溯：当前节点即将离开这条根路径，计数还原 prefix[cur] -= 1 dfs(root, 0) return self.ans

如果你用的是 Java，key 用 long 会更稳妥，因为虽然这题节点值范围小、int 够用，但很多改版题会把范围放大，提前用 long 能省一次返工。Python 没有这个问题，整数随便造。

4.2 三处容易被忽略的细节

第一，查表和入表的顺序不能反过来。必须先查 cur - targetSum，再把 cur 入表。如果先入表再查，当 targetSum 为 0 时，cur - 0 恰好等于 cur，而当前节点的前缀刚刚入表，你会把一条根本不存在的"空路径"额外算进去，导致答案偏大。就算 targetSum 不为 0，先入表也会让 map 里混入不属于当前路径前缀的信息，只是恰好查不到而已。所以这个顺序是硬性要求，不是习惯问题。

第二，用 self.ans 累加而不是让 dfs 返回计数值，纯属 Python 写法偏好，不是必须。用闭包变量的好处是每个节点只做"查一次表、加一次表、减一次表"三个动作，返回值随便写；坏处是面试时你得能解释清楚状态从哪来。如果你更习惯返回值写法，可以让 dfs 返回"当前子树内新增的命中数"，两种都行，但别在同一份代码里混着写。

第三，递归函数里 cur 是值传递，但 prefix 是引用传递。这恰恰是回溯能成立的前提：cur 跟着递归栈自动恢复，prefix 必须手动恢复。理解这一点，你就明白为什么"回溯只动 prefix，完全不用管 cur"。

4.3 时间与空间复杂度

时间上每个节点恰好访问一次，每次操作是哈希表的 O(1) 读写，总复杂度 O(n)。空间上哈希表最多存 n 个不同前缀和，加上递归栈深度（最坏 O(n)），总体 O(n)。和暴力解放到一起对比更直观：

5. 实测踩坑记录：漏答案和错答案都是怎么来的

5.1 漏掉 {0: 1}：所有以根为起点的路径直接消失

拿个最朴素的例子：根节点 5，左孩子 3，targetSum = 8。正确路径只有一条：5 → 3。跑前缀和解法时：走到根，cur = 5，查 5-8=-3，没有；走到节点 3，cur = 8，查 8-8=0。如果 map 里没有 {0: 1}，这次查表结果是 0，ans 一直是 0——明明正确路径就在眼前，却一条都数不出来。加上 {0: 1} 之后，这里一查就是 1。

我一开始写的时候甚至把 {0: 1} 写成了 {0: 0}，提交到第 40 多个用例才暴露。这种错误不是逻辑错误，是初始化错误，极其隐蔽，因为大部分测试用例里"根起点路径"和其他路径混在一起，少一条很难用肉眼发现。所以我的经验是：写完先跑几个"根直接通向目标"的小用例，专门验证这一行。

5.2 忘了回溯：左右子树互相串线，数出根本不存在的路径

构造一棵小树：根 0，左孩子 5，左孩子的左孩子 7；右孩子 10，右孩子的右孩子 8。targetSum = 6。手动数一遍，这棵树里没有任何一条下降路径的和等于 6，正确答案是 0。

错误写法是：访问完左子树后，不执行 prefix[cur] -= 1。那么走到右孩子 10 时 cur = 10，查 10-6=4 没有；继续走到右下节点 8，cur = 18，查 18-6=12——坏事了，map 里还留着左子树节点 7 的前缀 12（根 0 + 左 5 + 左左 7），于是错误地命中 1 次，ans 变成 1。这条"路径"如果强行解释，得从 7 跳到 8，中间还要经过不存在的边，实际在树里根本不存在。

这个例子我一直留着，因为它是回溯必要性的完美演示：不是"多算了一两条"，而是算出了结构上不存在的路径。每次重刷 437，我都会先跑一遍这个错误用例，确认回溯逻辑没写丢。

5.3 用集合代替计数哈希表：重复前缀被吞答案

题目没有规定节点值不能为 0，负数也会让同一条根路径上出现重复前缀和。用 set 存前缀和会丢掉"出现次数"，只保留"是否出现"，一旦某个前缀和在同一条路径上出现多次，就少算。

例子：根 0，右孩子 0，右孩子的右孩子 5，targetSum = 5。正确路径其实有 3 条：根 → 右 → 右右（0+0+5）、右 → 右右（0+5）、右右单独（5）。前缀和 0 在这条路上出现了 3 次（初始、根、右孩子），所以走到右右节点时 map[0] = 3，这才有 3 条。用 set 就只剩 1。计数哈希表把"出现次数"作为核心信息，这个信息在负数多的树上尤其重要。

5.4 负数与 targetSum = 0：别在递归里提前 return

暴力写法里最常见的 bug 是：_count_from 里一旦发现 remain == node.val 就返回，以为路径到底了。错。看一条链：5 → -2 → 2，targetSum = 5。合法路径有两条：单独一个 5，以及 5 → -2 → 2（5-2+2 还是 5）。如果你在节点 5 处发现 5 == 5 就 return，第二条路径就丢了，因为负数把和拉低之后又能拉回来。前缀和解法天然免疫这个坑：它从来不看"当前和是否已经达到目标"，只关心 cur - targetSum 在 map 里有没有。这就是前缀和把"路径长度不确定"这个麻烦直接吸收掉的原因——你根本不需要知道路径在哪里结束，只需要在当前节点结算"以我为终点能凑几条"。

6. 顺着 437 把路径类题目串起来复习

6.1 数组版同款：560. 和为 K 的子数组

437 和 560 是同一个套路在树和数组上的两种形态。560 的代码甚至短得离谱：

class Solution: def subarraySum(self, nums: List[int], k: int) -> int: prefix = {0: 1} ans = cur = 0 for x in nums: cur += x ans += prefix.get(cur - k, 0) prefix[cur] = prefix.get(cur, 0) + 1 return ans

区别只有一个：数组是顺序遍历，不需要回溯；树是 DFS，必须在递归返回时把前缀计数减掉。如果你 560 刷通了再来看 437，会发现 437 无非是"给 DFS 加了个回溯"而已；反过来，先刷 437 再刷 560，数组版会觉得异常简单。我建议这两题放到同一天做，前后对照效果最好。另外，前缀和这个套路在周赛里出现频率很高，不管套在数组、二叉树还是字典树上，核心都是 cur - target 查表，熟悉了之后一眼就能认出来。

6.2 面试作答顺序：先暴力讲清思路，再前缀和讲清优化

如果面试考到 437，我建议的作答节奏是：先花两分钟说暴力怎么做——外层枚举起点、内层向下 DFS，O(n²)；然后指出问题在于"每条路径的起点终点被重复枚举"，顺势引出前缀和。这样不仅展示了你对题目深度的理解，还给了面试官一个清晰的复杂度演进。直接把最优解拍上去当然也行，但少了对照，说服力会弱一截。

至于 124. 二叉树中的最大路径和，它虽然也是"任意起点、任意终点"，但问的是最大值而不是计数，解法变成了后序遍历返回子树贡献值，跟前缀和不是一个套路。别把所有"任意路径"题目都按前缀和硬套，先看清楚是计数、存在性还是最值。

6.3 复习顺序建议

我给自己定的复习路线是：112 → 113 → 437 → 560 → 124。前两题练"根到叶子"的递归基本功，437 引入前缀和和回溯，560 把同一套路切到数组验证理解，124 再升级到"任意路径最值"的树形 DP。这条线走完，二叉树路径类的核心考法基本全覆盖了。

最后说一个我自己的小习惯：每刷完这类"前缀和 + 树"的题，我会顺手把 map 初始化和回溯这两行单独抄进错题本，旁边标注它们的报错症状——一个是"答案整体偏小，根起点路径全部丢失"，一个是"答案莫名偏大，出现结构上不存在的路径"。下次再遇到任何树上前缀和的变体题，先检查这两行，能省下大量调试时间。