力扣437题解析：二叉树路径总和III的前缀和与回溯解法-北京尧图网络

力扣第437题——路径总和 III是我心里“二叉树上递归题”的一道分水岭。它挂在中等难度看起来和112、113同属“路径总和”家族但命题角度完全变了前两问要么问“是否存在一条从根到叶子的路径”要么问“把所有满足条件的路径列出来”而这一题直接改成“整棵树里到底有多少条方向向下的路径节点值之和恰好等于 targetSum”。路径的起点不一定是根节点终点也不一定是叶子节点这一下就把很多人从“背模板”的状态打回原形。这篇文章我打算从暴力解法讲起再把真正高频的套路——前缀和加回溯——完整推导一遍代码都给全最后补上我在实际刷题和面试复盘里踩过的坑。理解这道题之后你顺带也能把“和为 K 的子数组”那一类题目一起打通。1. 读懂“路径总和 III”问题定义和题目边界1.1 题目到底在问什么力扣官方的描述是给定一棵二叉树的根节点 root 和一个整数 targetSum求这棵二叉树里节点值之和等于 targetSum 的路径数目。路径不需要从根节点开始也不需要在叶子节点结束但是方向必须向下也就是只能从父节点走向子节点。这句话里有三个约束必须拆开看任意起点你可以从任意节点开始计数包括根节点也包括叶子节点。任意终点走到任意节点就可以停下来不要求必须是叶子节点。只能向下路径不能向上拐不能跨兄弟节点去组合也不能从左子树绕到右子树。这意味着我们在递归时只能沿着 parent - child 的方向延伸。只要选择了某个起点后面每一个节点都只能继续向左孩子或右孩子走一旦回头这条路径就失效了。这个“方向只能向下”的限制是整个题目的根基也是后面所有解法的前提。1.2 先看清题目的示例题目给的示例树长这样10 / \ 5 -3 / \ \ 3 2 11 / \ \ 3 -2 1targetSum 8 时答案是 3。三条满足条件的路径分别是5 - 35 - 2 - 1-3 - 11我建议拿到题之后先把这棵树画在纸上不写代码亲手把三条路径找出来。找完你会发现满足条件的路径大多藏在树的中间位置而不是从根出发。这和前面“路径总和 I / II”那种从根开始一路走到叶子的场景体感差别非常大。1.3 和前两题相比难在哪里112 路径总和只要求返回一个布尔值判断从根到叶子是否存在一条路径和为 targetSum。因为起点和终点都固定DFS 里维护一个剩余值就能解决。113 路径总和 II仍然是从根到叶子但要收集全部满足条件的路径所以要带着一个路径列表在 DFS 里做回溯把当前尝试过的节点加进去递归完再弹出来。437 路径总和 III起点和终点全部放开问题从“判断存在性”和“输出路径”变成了“统计数量”。如果没有前缀和意识很容易写出一个看起来很对的双重 DFS然后在复杂度分析那一步卡壳。这道题在面试里经常被当作“递归加数据结构”的综合考察点。很多候选人一上来就写从每个节点开始向下枚举的版本问复杂度时才发现一旦树退化成一条链时间会直接到 O(n^2)。所以正确思路不是硬往下递归而是想办法把“任意连续段求和”的问题转化成可以复用的信息。2. 暴力双 DFS先保证正确性2.1 思路拆解最简单也最符合直觉的思路每个节点都有资格成为路径的起点。于是外层遍历整棵树把每个节点都当作起点内层从起点出发沿着向下的方向延伸统计所有子路径的和等于 targetSum 的个数。这就是“双重 DFS”。第一层 DFS 负责枚举起点第二层 DFS 负责从某个起点向下延伸。每一层的动作都很朴素所以正确性非常容易验证。2.2 Python 参考实现from typing import Optional class Solution: def pathSum(self, root: Optional[TreeNode], targetSum: int) - int: if not root: return 0 # 第二层DFS以 node 为起点向下的路径中能凑出多少 remaining def dfs_start(node: Optional[TreeNode], remaining: int) - int: if not node: return 0 count 0 # 当前节点本身就能凑成一条路径计数加1 if node.val remaining: count 1 # 继续向左右子节点延伸 count dfs_start(node.left, remaining - node.val) count dfs_start(node.right, remaining - node.val) return count # 第一层DFS枚举每个节点作为起点 return ( dfs_start(root, targetSum) self.pathSum(root.left, targetSum) self.pathSum(root.right, targetSum) )代码里的self.pathSum(root.left, targetSum)不是多余的。它负责把左孩子也当成新的起点再执行一次完整的起点枚举。右孩子同理。所以每个节点都既会被外层当成起点也会被内层当成某个起点路径上的中间节点这种重叠枚举正是题目要求的“任意起点”特性。2.3 复杂度分析时间上在平衡二叉树中每个起点向下延伸的平均深度大约是 O(log n)所以整体时间复杂度是 O(n log n)。但是当树退化成一条链表时起点有 O(n) 个每个起点向下最多延伸 O(n) 层整体就变成 O(n^2)。力扣虽然给了 1000 个节点的规模O(n^2) 在很多用例下也勉强能过但那是因为数据没有刻意刁难。如果面试官让你分析复杂度你必须主动说出退化情况。空间上递归栈最深是树的高度最坏也是 O(n)。这个暴力版本不是最优解但它有一个巨大优点逻辑简单适合作为和正确答案对拍的参考实现。我自己在写前缀和解法之前就先用这个版本跑了一遍题目的示例确认了整体流程。2.4 这里有一个容易懵的点很多初学者看到self.pathSum里又调用了self.pathSum会怀疑是不是重复计算。这里要明确第一层递归枚举的是起点第二层递归负责累计一段路径的和两者职责不同。重复的只是每个节点既当起点又被访问但这不是真实路径只是枚举组合。暴力解法本质上是枚举“起点”和“终点”的全部配对组合所以正确。不过既然暴力能过为什么还要学前缀和因为树的深度一旦拉到接近上限O(n^2) 就不稳定了。更关键的是前缀和思路是这一类“连续段求和”问题的通用模板学会它能直接迁移到其他题目。3. 前缀和加回溯把时间复杂度压缩到 O(n)3.1 前缀和怎么和树扯上关系先看数组版本给定一个数组 nums 和整数 k问有多少个连续子数组的和等于 k。如果依次求出前缀和 prefix[i]那子数组 [l, r] 的和就是 prefix[r] - prefix[l-1]。所以我们真正要找的是有多少对前缀和之差等于 k。用一个哈希表记录前缀和出现的次数一次遍历就能完成。这就是 LeetCode 560 题“和为 K 的子数组”的标准解法。树上的 DFS 天然形成一条“从根节点到当前节点”的链。链上的每个节点都对应一个前缀和这个概念和数组里的前缀和完全一一对应。唯一的差别是数组是线性的从左往右扫一遍不会回头树分叉之后你会从左分支回到父节点再进入右分支所以必须把左分支里的前缀和从哈希表里撤销否则右分支会误以为左分支的路径和自己在同一条链上。3.2 核心公式假设当前 DFS 访问到节点 nodecurrent_sum表示从根节点到 node 这条链上所有节点值的累加和。以 node 作为路径终点、起点在这条链上某个位置的路径如果路径和正好等于 targetSum就等价于current_sum - old_target targetSum移项得到old_target current_sum - targetSum也就是说只要哈希表里记录过 root 到当前节点这条路径上出现过的所有前缀和那么current_sum - targetSum的出现次数就等于以当前节点为终点的满足条件的路径条数。把所有节点作为终点时的满足路径数累加就是整棵树的答案。有两个边界必须严格注意哈希表初始要放{0: 1}它表示“空路径”的前缀和是 0用来统计从根节点出发的整条路径。查询必须发生在把current_sum写入哈希表之前否则 targetSum 等于 0 时会把“当前节点到自己”这种长度为 0 的假路径也算进去。3.3 为什么回溯必不可少如果不做回溯第一次 DFS 进入左分支时记录的前缀和在返回父节点之后仍然留在哈希表里。当后续 DFS 走到右分支的某个节点时它就会误以为左分支的前缀和和当前节点在同一个根到节点的链路上从而组装出一条根本不存在、横跨左右分支的路径。这类错误最典型的表现就是最终答案偏大而且树越复杂偏得越离谱。所以左右子树递归完成之后必须把当前节点写入的那个前缀和计数减掉。如果减到 0可以直接删除键也可以保留值为 0 的键查询时getOrDefault返回 0不影响结果。我建议真正编码时删除键这样调试打印哈希表时不会产生误导。3.4 完整 Python 实现from typing import Optional class Solution: def pathSum(self, root: Optional[TreeNode], targetSum: int) - int: ans 0 # 前缀和 - 出现次数 # 初始 0 - 1 代表空路径用于统计从根出发的整条链 prefix_sums {0: 1} def dfs(node: Optional[TreeNode], current_sum: int) - None: nonlocal ans if not node: return # 每走到一个节点就把节点值累加进当前前缀和 current_sum node.val # 关键点先查询后写入哈希表 ans prefix_sums.get(current_sum - targetSum, 0) # 把当前前缀和记录进去供后续子节点查询 prefix_sums[current_sum] prefix_sums.get(current_sum, 0) 1 dfs(node.left, current_sum) dfs(node.right, current_sum) # 回溯当前节点处理完必须把计数减掉 prefix_sums[current_sum] - 1 if prefix_sums[current_sum] 0: del prefix_sums[current_sum] dfs(root, 0) return ans递归入口传入的current_sum是 0根节点的值在第一次递归里累加这样的设计是为了让prefix_sums里的{0: 1}能服务于根节点本身。如果你改成在调用前就把 root.val 传进去逻辑会乱不建议。3.5 手动走一遍示例树我用上面的代码把示例树的访问顺序拉出来只看对最终答案有贡献的节点访问节点当前累加和查询的旧前缀命中次数对应路径101020无51570无35的左子181015 - 333的左子21130无-21680无21790无1181015 - 2 - 1-37-10无1118101-3 - 11三次命中正好对应题目示例里的三条路径。注意表中的 21、16、17 这些前缀和在对应节点递归结束返回时就被删除了所以访问 2、1 以及 -3、11 时哈希表里不会残留左分支的旧前缀和。这就是回溯的现场效果。4. 工程细节查询顺序、负数节点、溢出处理4.1 “先查询再更新”是命门这一点值得单独拎出来说。当前节点进入函数后先把 node.val 累加进 current_sum然后立刻查询current_sum - targetSum。为什么必须这样如果先把 current_sum 写入哈希表再查询当 targetSum 等于 0 时查询current_sum - 0会把刚刚插入的 current_sum 也查出来这就凭空多出一条“当前节点到自己”的长度为零的假路径。举个最极端的例子单节点树 root [0]targetSum 0正确答案应该是 1因为节点 0 本身的值就是 0。顺序写反的话你会得到 2。这个用例我在本地加进自测清单后再也没犯过顺序错误。4.2 哈希表计数必须用次数不能用集合有些同学觉得用 Set 记录“出现过的前缀和值”就够了。这个想法在节点值全为正数时碰巧能过但只要路径里出现负数同一个前缀和很可能在同一条路径上多次出现。比如路径 1 - -1 - 0targetSum 0。手数一下满足条件的路径[1, -1]、[1, -1, 0]、[0]一共 3 条。用 Set 记录前缀和时因为前缀和 0 早就出现过第二次、第三次需要重复计数的情况做不到只能统计 2 条。原因就是 Set 只记录存在性不记录次数。同一个前缀和出现多次意味着有多个不同起点都能和当前终点组成满足条件的路径所以必须用“前缀和 - 次数”的哈希表。4.3 数值溢出和语言差异力扣的节点值范围是 -10^9 到 10^9节点数最多 1000因此 current_sum 完全可能达到 10^12 级别。Python 的 int 是任意精度所以直接写没问题。Java 和 C 如果用 int 累积就可能出现整数溢出导致答案变成负数或者莫名其妙的大数。面试用 Java 时我建议 HashMap 的键和递归参数都用 longclass Solution { private int target; private int ans; private MapLong, Integer prefixSums new HashMap(); public int pathSum(TreeNode root, int targetSum) { this.target targetSum; prefixSums.put(0L, 1); dfs(root, 0L); return ans; } private void dfs(TreeNode node, long currentSum) { if (node null) return; currentSum node.val; ans prefixSums.getOrDefault(currentSum - target, 0); prefixSums.put(currentSum, prefixSums.getOrDefault(currentSum, 0) 1); dfs(node.left, currentSum); dfs(node.right, currentSum); int count prefixSums.get(currentSum) - 1; if (count 0) { prefixSums.remove(currentSum); } else { prefixSums.put(currentSum, count); } } }Java 版本里我特意把回溯写成了“减到 0 就删除”的形态避免哈希表里出现一堆值为 0 的键。4.4 回溯计数减到 0 后的两种做法有人在回溯时直接写成prefix_sums[current_sum] - 1但不删键。这样做不会出错因为查询用的是getOrDefault对于一个值为 0 的键返回结果同样是 0。但问题在于调试时哈希表里残留很多值为 0 的键你很难分辨哪些前缀和真的出现在当前路径上。我自己的习惯是减到 0 就del这样每一个时刻哈希表里存活的键都精确对应当前这条链上出现过的有效前缀和排查问题会清晰很多。5. 变体题与面试答题模板5.1 路径总和家族横向对比题目起点终点返回结果核心技巧112 路径总和根节点叶子布尔值DFS 维护剩余值113 路径总和 II根节点叶子所有路径列表DFS 回溯保存路径437 路径总和 III任意节点任意节点向下路径数量前缀和回溯哈希表这个表把问题差异摆得很清楚。437 的难点并不在于递归本身而在于“任意起点”把之前固定的根节点前缀信息变成了需要动态维护的集合。5.2 从树到数组一套模板通用前缀和加哈希表模板并不只适用于树。数组场景下LeetCode 560 题“和为 K 的子数组”就是一模一样的思路class Solution: def subarraySum(self, nums: List[int], k: int) - int: prefix_counts {0: 1} cur 0 ans 0 for num in nums: cur num ans prefix_counts.get(cur - k, 0) prefix_counts[cur] prefix_counts.get(cur, 0) 1 return ans对比 437 的代码核心结构惊人一致先累加再查旧前缀再写新前缀。数组版本不需要回溯因为数组是线性顺序不会出现分支串扰树版本必须回溯因为树有分支。理解和记住这个差异你就同时掌握了两道题。5.3 如果面试官要你输出具体路径怎么办前缀和方案只统计数量哈希表里并不保存某个前缀和对应的具体起点。如果要连路径一起输出我建议回到 DFS 加回溯的思路维护一个从当前根向下的节点列表每次进入新节点时从列表尾部倒着遍历把每一段连续路径的和都算一遍等于 targetSum 就记录这条路径。树深度最多 1000倒序遍历的代价可以接受而且代码逻辑非常直接。面对扩展题这是一个靠谱的兜底方案。5.4 面试里的推荐讲法我建议按照“审题 - 暴力 - 前缀和优化 - 编码 - 复杂度”五步来讲先说明题目限制任意起点、任意终点但方向必须向下。把问题理解成统计若干条垂直向下的连续链段。给出暴力思路枚举起点向下延伸复杂度 O(n^2)。指出链上的累计和可以用前缀和相减树的 DFS 天然形成一条链。说明哈希表存前缀和出现次数配合回溯。写代码时重点展示“先查询再更新”和“回溯删除”最后报出时间 O(n)、空间 O(n)。这种讲法既有层次又能让面试官看到你从暴力到优化的完整思考过程。6. 踩坑实录与自测清单6.1 我实际踩过的三个坑坑一刚写前缀和解法时忘了在递归结束后把 prefix_sums[current_sum] 减回去结果答案偏大。后来我在代码里打印哈希表发现左分支的数据一直泄漏到右分支才明白回溯是树版本前缀和的核心不是可有可无的修饰。坑二第一次用 Set 做哈希表遇到带负数的用例怎么跑都对不上暴力解。后来用1 - -1 - 0targetSum 0 这个用例手工推了一遍才发现问题出在“存在性”和“次数”的区别上。从那以后我默认用字典记录次数彻底不用 Set。坑三用 Java 实现时没注意溢出构造一条长链测试用例时答案直接变成负数。把 HashMap 的键和递归参数都改成 long 之后才恢复正常。这个问题在本地测试不容易暴露但面试官只要构造一组大数据就会立刻发现。6.2 本地自测清单每次写完 437 的解法我都会跑这几组用例空树root NonetargetSum 任意输出 0。单节点等于 targetroot [1]targetSum 1输出 1。单节点为 0root [0]targetSum 0输出 1。这组用例专门验证“先查询再更新”。负数路径构造 1 - -1 - 0 这样有正有负的链验证哈希表计数的次数逻辑。退化链表1 - 2 - 3 - 4确认不会在时间复杂度上卡死。题目示例树targetSum 8验证输出 3。如果你本地有暴力版本可以写一个简单的对拍函数随机生成二叉树比较暴力解和前缀和解的结果。这是最稳的验证方式。6.3 如果限制条件继续放宽如果题目改成“任意起点、任意终点且不再限制方向”那这道题就从简单的 DFS 升级成了树上的路径统计问题通常要用到奇偶深度或者更复杂的树上差分技巧。实际面试很少直接出到那一层但理解“向下限制”如何让前缀和方案成立能帮助你在遇到新题时更快判断能不能套用这个模板。我把这道题吃透后最大的感受是不要急着背结论而是先把暴力和前缀和两版都写一遍再用示例树手动走一遍。只有当你亲眼看到从根出发的前缀和和中间某一段路径建立起减法关系后续遇到类似题目才真正有把握。网上很多模板只给结论偏偏忽略了回溯这个树上前缀和和数组前缀和最大的区别。把这一点想明白437 这道题就算真正过关了。

力扣437题解析：二叉树路径总和III的前缀和与回溯解法

相关推荐

S7-200 SMART通信协议详解：S7、Modbus与自由口实战指南

Agent技能化实战：从单体烂摊子到标准化技能体系的设计与落地

浏览器插件ponytail：技能包机制与网页信息自动化整理

更多资讯

Python自动化Excel数据清洗与汇总实战

从“干完再发照片“到“每一步都能被确认“：异地交付的三段闭环，附 4 条可复制提示词

罗伊氏粘液乳杆菌：肠道健康的微生物守护者

值班大屏实战指南：轻量级工业可视化系统部署与信创适配

Web滚动性能优化与渲染管线深度解析

AB测试分层抽样实战：解决随机分组的样本偏差问题

今日更新

小波包能量谱原理与MATLAB实现：从频带分解到故障特征提取

基于LSTM的网易云音乐评论情感分析：数据清洗与模型调优实战

Alpha-Beta剪枝与极大极小值算法：博弈树搜索原理与实战优化

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？