路径总和 III 前缀和优化：从暴力深搜到 O(n) 解法

1. 从“路径总和”到“路径总和3”：这题到底在考什么

力扣热题100里的第48题“路径总和3”是很多人的分水岭。前面两题只要会简单的递归就能过，这道题却突然跳出了“根到叶子”的框框，要求统计的是任意节点向下到任意节点的路径和。第一次看到基本都会愣住：这怎么数？暴力遍历每个节点往下去找有没有路径能凑够targetSum，复杂度显然上去了；想优雅一点就要引入前缀和，把树上路径问题变成“两段前缀和的差”问题。

先明确这题在说什么。给定一棵二叉树和一个目标值targetSum，统计这棵树里有多少条路径的节点值之和等于targetSum。路径要求是“从上往下”的，也就是说起点可以是任意节点，终点必须在这个节点的某个后代方向上，路径可以不经过根节点，也完全不要求到达叶子。这比“路径总和”和“路径总和2”都自由得多，统计口径也完全不同。

一个很自然的朴素想法是：分别以每个节点作为路径的起点，向下去做深度优先搜索，枚举所有能形成的路径。如果当前这条路径的累加和刚好等于targetSum，就计一次数。这种思路实现简单、正确性好，但时间复杂度并不乐观，最坏会到O(n²)。很多新手一开始觉得题目规模不大无所谓，可一旦遇到一条链形的树，这种暴力写法就会感受到明显的压力。

于是就有了前缀和优化法。核心思想是：从根出发到任意节点，都能记一个“路径前缀和”。如果某个祖先节点的前缀和是A，当前节点的前缀和是B，那么从那个祖先节点的下一个节点到当前节点这一段的路径和，就是B - A。这样一来，只要在深搜过程中用哈希表记录“某个前缀和出现多少次”，就能以O(1)的时间判断当前节点到某些祖先之间是否存在满足条件的路径，整棵树只需要遍历一次。

这篇文章面向的读者，是已经能独立解出“路径总和”和“路径总和2”，但看到这题不知道如何下手的同学；也适合那些面试前想集中补一下深搜、递归、前缀和这类基本功的开发者。我会先展开两类解法的原理，再给出可直接运行的代码，最后把几个容易踩的坑和排查方法整理出来。

2. 思路拆解：暴力深搜为何可行，前缀和为何更优

2.1 从“每个节点作为起点”来理解暴力深搜

先聊暴力法。如果题目让我们统计“以某个固定起点s开始的路径中，有多少条路径和等于targetSum”，这个问题其实很单纯：从s一路深搜下去，每次累加当前节点的值，遇到等于targetSum就计数一次。因为树里可能存在值为负的节点或0，累加和达到targetSum之后继续往下走，后面的路径仍然有可能再次达到targetSum，所以不能提前停止，而是要完整遍历s的所有向下路径。

把起点从“固定一个”扩展成“任意节点”，只需要在外面套一层遍历：对每个节点，都执行一次“以该节点为起点向下统计”的逻辑。这就是双重递归的暴力写法。外层递归负责切换起点，内层递归负责从起点向下枚举所有可能路径。

这个方案的时间复杂度需要仔细算一下。内层统计一个起点时，最坏会访问以该起点为根的子树上所有节点，代价是O(子树规模)。那么把所有节点作为起点都做一遍，总代价相当于对树上每个节点，把它的所有后代节点都访问一遍。在最不平衡的情况下，也就是树退化成一条链的时候，第一个起点要往下扫n个节点，第二个要扫n-1个，依此类推，总复杂度就是O(n²)。

优点是逻辑非常直观，几乎不需要什么前置知识，也不容易写错。缺点是n很大或者面试官要求优化时，这个复杂度解释起来不够漂亮。

注意：很多刷题文章里讨论的“普通深搜”有两种理解。一种就是我上面说的，外层遍历节点起点，内层统计路径；另一种是从每个节点向上回溯父节点，检查是否存在链上和为targetSum。两种都能做，但代码形态差异很大。力扣题解里常见的“双重递归”结构，指的多半是第一种。

2.2 前缀和优化到底优化了什么

前缀和解法的本质是把“路径和等于targetSum”这个判断，转化成了“两个前缀和之差等于targetSum”的判断。

想象我们维护一个数组，这个数组是从根节点到当前节点路径上的所有节点值。那么这棵树上任意一条向下的路径，都可以看成这个数组的一个连续子段。问题就变成了：给定一个数组，统计有多少个连续子段的和等于targetSum。数组统计连续子段和，经典做法就是前缀和加哈希表。前缀和数组pre[i]表示前i个元素的和，那么pre[j] - pre[i]就是第i+1到第j个元素的连续子段和。要让这个值等于targetSum，等价于pre[j] - targetSum = pre[i]。于是在扫描到第j个位置时，只要知道前面有多少个位置的前缀和等于pre[j] - targetSum，就能直接知道以第j个元素结尾的合法子段数量。

把数组的手段搬到树上时，思路完全一致。从根节点向下走到任意节点，路径前缀和是不断累加的。当深搜到达节点node时，我们用哈希表记录“从根到当前节点这条路径上，各个前缀和分别出现多少次”。然后查询current_sum - targetSum在表里出现的次数，这个次数就是以当前节点为路径终点、且满足和为targetSum的路径数量。把所有节点作为终点时统计到的数量加起来，就是最终答案。

这里有一个容易绕晕的细节：为什么查询结果是“以当前节点为终点”的路径数？因为前缀和表里记录的是从根到当前节点的祖先链上的前缀和。假设某个祖先节点祖先A的前缀和是x，当前节点node的前缀和是cur，如果cur - x = targetSum，那么从A的下一个节点到node的节点值之和就是targetSum。由于A的“下一个节点”方向唯一，A的每个不同深度都对应一条不同的路径。哈希表里x出现了几次，就说明有几种不同深度的祖先能让当前节点形成合法路径。自然地，这些路径的终点都是当前节点node。

有的读者可能会问：那路径的起点是根节点的情况怎么处理？答案就是初始化哈希表时放入{0: 1}。这个0表示一个虚拟的“根之前的起点”，这样当某个节点本身从根到它的前缀和恰好等于targetSum时，cur - 0恰好命中，这条“从根开始”的路径就能被正确计数。

2.3 回溯与状态还原：前缀和实现的灵魂

树上的深搜和数组里从左到右扫描有一个关键差异：数组从左往右是不会回头的，但树有分叉。假设当前走到了某个分支的深处，哈希表里记录了这条分支所有节点的前缀和。如果此时直接跳到另一条分支继续算，而不做任何状态清理，那么另一条分支在查询时，会把不属于自己祖先节点的前缀和也算进去。这样会把不同路线上的节点错误地拼成路径，答案就会失控。

解决办法是回溯。在递归进入某个节点、完成它所有子树的处理之后，必须把自己这个节点对哈希表造成的影响撤销掉。也就是说，假如进入节点时我们把当前前缀和的计数加1，那么从这个节点返回父节点之前，要把这个计数减回去。这样才能保证哈希表在任何时刻都只记录着“从根到当前递归栈顶层节点”这一条链上的前缀和，而不会残留其他已经遍历完的分支的信息。

所以这段代码的dfs模板很像二叉树路径搜索里的“进入时修改状态、返回时恢复现场”经典模式。这也是为什么我把前缀和优化称为“深搜加前缀和”，因为它不是单纯的前缀和，深搜的状态管理才是能否写对的关键。

3. 具体实现：先写出朴素深搜，再升级前缀和

3.1 暴力版本的完整写法

以“每个节点作为起点”的版本为例，代码非常短。

class Solution: def pathSum(self, root: TreeNode, targetSum: int) -> int: if not root: return 0 # 计算从 node 出发，向下的路径里有多少条和为 targetSum def count_down(node, cur_sum): if not node: return 0 cur_sum += node.val # 当前和已经满足则算1条，不满足则算0条 res = 1 if cur_sum == targetSum else 0 # 因为节点值可以为负，即使满足条件也还要继续往下走 res += count_down(node.left, cur_sum) res += count_down(node.right, cur_sum) return res # 外层：枚举每个起点 ans = count_down(root, 0) ans += self.pathSum(root.left, targetSum) ans += self.pathSum(root.right, targetSum) return ans

这里有个非常典型的坑：count_down里不能因为cur_sum == targetSum就返回，因为接下来如果碰到值为负数或者0的节点，累加和仍然有可能再次等于targetSum。很多从数组“两数之和”转过来的同学在这里会惯性剪枝，导致结果偏小。

另一个需要注意的点是：外层的递归结构里，我直接调用了self.pathSum，这意味着每到一个节点，都要重新递归它的左右子树来枚举起点。这个递归结构本身就是“路径总和3”这个暴力方案的经典形态，写起来很顺手，但要是忘了处理root.left和root.right的起点枚举，就会漏掉大量非根起点的路径。

3.2 前缀和优化版本的完整写法

把深搜、前缀和、回溯整合到一起，代码如下：

class Solution: def pathSum(self, root: TreeNode, targetSum: int) -> int: # 前缀和哈希表，key是前缀和，value是出现次数 prefix_sum_count = {0: 1} self.ans = 0 def dfs(node, cur_sum): if not node: return cur_sum += node.val # 关键：查询的是 cur_sum - targetSum 出现了多少次 need = cur_sum - targetSum self.ans += prefix_sum_count.get(need, 0) # 将当前前缀和登记到哈希表 prefix_sum_count[cur_sum] = prefix_sum_count.get(cur_sum, 0) + 1 # 递归处理左右子树 dfs(node.left, cur_sum) dfs(node.right, cur_sum) # 回溯：从当前节点返回前，撤销它带来的计数增加 prefix_sum_count[cur_sum] -= 1 # 如果减到0，可以保留键值，也可以删除，留着不影响正确性 # 不过为了内存舒适，也可以在这里判断后删除 dfs(root, 0) return self.ans

这段实现的执行顺序特别重要：必须是先查询need，再登记当前前缀和。原因在于路径要求至少包含一个节点，不能用当前节点自己和自己组成一条长度为0的路径。如果先插入当前前缀和再查询，当targetSum为0时，每次都会被自己额外算上一次，答案就虚高了。

我见过有些人会习惯性地删掉计数为0的key，像这样：

prefix_sum_count[cur_sum] -= 1 if prefix_sum_count[cur_sum] == 0: del prefix_sum_count[cur_sum]

这样写也不会错，反而能让哈希表更小一些。力扣上用不带删除的写法更常见，因为查询时用get取不到就返回0，效果一样。不过如果你很在意递归返回时的状态绝对干净，用删除版本更符合“现场还原”的直觉。

3.3 “查表-入表-回溯”顺序的现场推演

为了说清楚顺序为什么不能乱，我模拟一个最简单的场景。

假设树只有一个节点，值是5，targetSum是5。正确流程：

1. 进入根节点，cur_sum变成5。
2. need = 0，查表得到prefix_sum_count[0] = 1，所以答案加1。这代表“从根到自己”的路径。
3. 登记cur_sum=5，表变成{0:1, 5:1}。
4. 叶子节点返回前，把5的计数减回去，表回到{0:1}。

如果顺序倒过来，先把cur_sum=5登记进去，再查need = 0，那依然是命中前缀和0，答案还是1，这里不会出错。真正出事的是当targetSum = 0，例如树只有一个节点5，目标0。正确流程：

1. 进入根节点，cur_sum变成5。
2. need = 5，查表得到0，答案不变。
3. 登记cur_sum=5，表变成{0:1, 5:1}。
4. 返回。

但假如先登记再查询，进入根节点时cur_sum变成5，先登记5，然后查询need=5，此时表里有5，就会错误地认为存在一条从某个祖先到当前节点的空路径，答案多算1。如果每个节点的targetSum都是0，这种错误会累积成节点总数，非常隐蔽。

所以我的建议是：把“先查表，再入表，返回前撤销”这句话当成固定模板记忆，不要因为某些示例不报错就随意调换。实际生产里如果写成维护全局cur_sum的方式，同样要注意先判断后更新状态。

3.4 两种解法的复杂度对比与适用场景

暴力解法的内层递归，对于起点为根节点的子树，最坏情况下会遍历整棵子树的所有节点；外层又会对每个节点调用一次，相当于把一个节点的所有祖先、后代关系全部枚举了一遍。因此总时间复杂度是O(n²)，空间复杂度是递归深度O(h)，其中h是树高。

前缀和解法每个节点只进入和退出一次，每个节点上只做常数次哈希表操作，时间复杂度是O(n)，空间复杂度同样是O(h)，额外的哈希表最大会保存从根到叶子路径上所有不同的前缀和，所以也是O(n)。

在数据规模较小时，两种解法差别不大。力扣里树的节点数通常能达到几千甚至上万，n²在极端链状数据下会明显超时。前缀和解法的优势不只是“快”，更关键的是思路本身可以推广到很多其他树形统计问题。

补充一下：如果面试中你先给出暴力解，再讲前缀和优化，本身就是一条很漂亮的思考路径演进过程。面试官更希望看到的是“能发现原方案的瓶颈，并有意识用数据结构去优化”，而不是一上来就背出最优解。

4. 实操中的高频报错与排查方法

4.1 常见问题速查表

4.2 我实际调试时被坑过的细节

第一个坑出现在前缀表的生命周期管理上。最初我尝试不把哈希表作为闭包变量，而是作为dfs的参数传入子节点。但由于Python中字典是可变对象，子节点对字典的修改会直接作用到同一个字典上。如果我在返回时忘了减回去，那这条分支留下的key到了另一条分支仍然存在。这就会导致统计出跨越两条分支的“伪路径”。后来我要求自己在每次写完递归函数后，都刻意检查“我在递进时修改了哪些状态，返回时是否还原了所有状态”，这一招对所有回溯和树形DP都管用。

第二个坑是空树时的边界。很多人会直接让dfs里处理空节点返回，但外层一开始就用了prefix_sum_count = {0: 1}，所以对空树来说，如果不加保护，答案会错误地变成1。正确做法是在入口判断if not root: return 0，或者让dfs内部对空节点直接返回且不进入查询逻辑。我倾向于前者，因为简单直观，也不会让后面的递归逻辑被空节点干扰。

第三个坑是递归返回值的风格差异。有些题解把dfs写成返回int，让每层统计累加后返回给上层；有些题解则维护一个外部变量self.ans，dfs只负责累加。两种风格在力扣都能通过。但如果你偏爱返回int的写法，要特别注意合并左右子树的返回值时不要重复统计当前节点。我在写“以每个节点为起点”的纯递归版本时，习惯把每一层的结果相加返回；而写前缀和版本时，用外部变量更顺手。你可以根据自己的习惯选择，建议不要在同一题里混用两种风格，很容易把自己绕晕。

第四个坑是数字范围。targetSum和节点值虽然都在32位整数范围内，但累加前缀和可能超过int32范围。Python的int没有溢出问题，但如果你用C++写，一定要用long long类型，否则链状树一累加就可能溢出，答案直接错误。这个细节在面试用Java或C++时会格外容易被忽略。

4.3 排查思路：构造样例反推逻辑

遇到答案不对时，我习惯先不急着print，而是挑几个“高灵敏度”用例来跑：

• 单节点，值等于targetSum。验证根节点到自身的路径是否能被统计。
• 单节点，值不等于targetSum。
• targetSum = 0，树上只有一条链，全部节点值都为0。
• 树中节点值有正有负，验证“不能提前剪枝”。
• 空树。

如果这些用例全部通过，一般核心逻辑就没有问题。剩下的多分支用例，可以再配合print关键变量快速定位。树形递归问题用print调试非常有效，只用在dfs开头打印当前节点、cur_sum、query结果、prefix_sum_count的状态，基本能一眼看出是哪一步漏了。

5. 延伸视角：这题背后的一类题型思路

路径总和3带出来的前缀和思路，在多种“子树”“子数组”“路径”问题上都通用。比如如果一个问题是统计二叉树里有多少条路径的和正好等于target，但节点值是正的，就可以在深搜时维护一个队列并用滑动窗口解决；如果节点值有正有负，前缀和哈希表是更稳妥泛用的方案。再比如把树的场景换成数组，统计一个数组中连续子数组和为K的个数，也能用几乎一样的前缀和哈希表方法。理解了这题，相当于把数组前缀和技巧移植到了树上。

我自己刷题过程中的体会是：二叉树问题里，递归函数中需要修改外部状态时，一定要把“进入递归前修改的状态”和“递归返回后恢复的状态”在代码里成对出现。前缀和哈希表在深搜中的应用，本质就是回溯法的状态管理。如果掌握了这一点，再去看“复原IP地址”“括号生成”“组合总和”这些回溯题，会发现思路完全是相通的。

回到力扣100这道题，我对它的定位是“树形题目面试高频必练”。它既考察你对二叉树递归结构的掌握，也考察你是否能把数据结构（哈希表）和递归状态维护结合起来。如果你能不看题解就写出前缀和版本，并且能解释清楚为什么需要先查表再入表，以及为什么需要回溯撤销，那这类题基本就稳了。

最后分享一个我在面试现场比较受用的表达方式：在讲暴力解时，可以把时间复杂度、可优化点讲清楚，然后自然引导出前缀和的动机——“我们需要避免对每个起点都做一次O(n)的扫描，那么是否能在一次遍历中同时记录所有历史前缀和，利用差值判断路径和？”这种表达会让面试官感受到你不只是在背模板，而是在真正思考。