如果说二叉树题目里最容易让人眼高手低的LeetCode 113 的“路径总和 II”绝对算一个。原因很直接你光会“递归求和”不够还得真正理解回溯把走过的路径一条一条收回来好在它的难度又不算高不像后面那些多层剪枝的题特别适合拿来找回溯的手感。另一个让我印象很深的点是热搜里那个高频问题——写二叉树程序时为什么总是报运行时错误几乎每个人在刷这道题时都会撞上一遍空指针没判、叶子节点判断写错、路径引用没拷贝、递归深度过大直接爆栈一个都不少。这篇文章就以 113. 路径总和 II 为对象把二叉树遍历、路径记录、回溯撤销、复杂度分析、常见运行时报错一条条拆开讲透给正在刷题或者准备面试的朋友一份可以直接对照复现的完整记录。不管你是第一次接触回溯还是已经能轻松秒掉第一题“路径总和”这篇都能给你一点不一样的视角。1. 先拆题路径总和 II 到底在考什么1.1 题目里的三个关键条件很多朋友一上来就急着写递归结果边界条件反复错。我的建议是先把题目翻译成人话。给定一棵二叉树给定一个整数目标值 targetSum要求返回所有从根节点到叶子节点的路径并且这条路径上所有节点值之和要等于 targetSum。这三个条件是层层嵌套的漏掉任何一个都会出错。第一个条件“根节点到叶子节点”意味着终点必须是叶子也就是左右孩子都为空的节点。第二条“路径上的节点值之和等于目标值”要求你在递归过程中不断累加或做减法走到叶子时判断当前累计结果。第三条“返回所有路径”这是和第一题最大的区别也是整道题的核心难点你不光要判断存在不存在还得把具体的路径列表保存下来。我在面试中问过不少候选人他们能把“判断是否存在路径”的递归写法背得很熟但一看到“返回所有路径”就卡壳。为什么因为判断存在性时你只需要在左子树或右子树找到一个可行答案即可而收集所有路径必须把左右两边都完整搜完并且要精确地维护一条“当前正在走的路径”。这就是典型的回溯场景。1.2 比第一题“路径总和”多了什么第一题“路径总和”大家应该很熟它是判断二叉树中是否存在根到叶子的路径路径和等于目标值。经典递归写法是def hasPathSum(root: Optional[TreeNode], targetSum: int) - bool: if root is None: return False if root.left is None and root.right is None: return targetSum root.val return hasPathSum(root.left, targetSum - root.val) or hasPathSum(root.right, targetSum - root.val)这里有个非常舒服的写法把目标和递归地减去当前节点值到叶子时直接判断是否相等。这个减法思路在第二题里同样适用但第二题你不能再“或”短路了因为左右子树都可能存在合法路径必须两边都走完。更关键的是布尔题不需要记录路径递归返回时不会留下任何“痕迹”而第二题要求你维护一个共享的路径列表遍历完左子树回到当前节点时如果不清除左子树节点右子树的路径里就会混入不属于它的节点。这就是为什么需要用回溯而不是简单递归就能糊弄过去。1.3 为什么说这道题是回溯的入门必刷题回溯这个词听着玄乎其实可以理解成“试探性前进不行就退回来”。想象你在山里徒步从一个岔路口往左走走到底发现不是目标目的地你会原路返回到岔路口再往右走。关键是什么是你返回的时候不会把左边那条路的路标也带在身上。递归中的 path 列表就相当于你的路标当你回到岔路口时必须把属于左分支的节点从 path 中弹出去否则再往右走时路标就混了。这道题特别适合作为回溯入门题因为它没有复杂的排列组合、没有“是否使用当前元素”的多层决策逻辑主线非常单纯沿着二叉树从上往下递归每当进入一个节点就 append每当离开一个节点就 pop。你把这两行代码的位置理解透以后再写全排列、组合总和、子集等问题会轻松很多。因为那些题的底层也是同一套逻辑只是决策空间更抽象了。1.4 和常见二叉树概念的关系遍历、深度、搜索树、线索树聊到二叉树题目很多人会把“搜索二叉树”“线索二叉树”“二叉树的深度”这些概念混在一起。其实它们都是不同的视角。路径总和 II 本质上是深度优先遍历的一种应用你必须先访问当前节点再去递归左右子树这正是前序遍历的顺序。为什么一定要前序因为路径本身就是从根出发往叶子走的天然适合前序。二叉树的深度在这里主要影响递归栈的深度。如果这棵树退化成了链式结构高度接近节点总数递归深度会非常大可能触发语言层面的递归上限。这个问题后面我会专门讲。搜索二叉树通常也叫二叉搜索树BST的特点是左小右大适合做查找和范围查询。但路径总和 II 不依赖节点的大小关系所以如果面试官换了一棵 BST 给你你也不能用“当前值大于剩余值就剪枝”这种思路去优化因为题目没有规定节点值是正数。线索二叉树则是一类利用空指针记录前驱后继的结构和这道题本身没有直接关系但可以和 O(1) 空间的遍历方式联系起来我放到扩展章节讲。2. 核心解法细节为什么必须用回溯2.1 递归函数的参数设计代码写得好坏一半看参数设计。路径总和 II 的递归函数我习惯设计成这样def dfs(node, remaining, path, result):四个参数分别表示当前节点、剩余的目标值、当前路径列表、最终结果容器。这里的 remaining 是 targetSum 减去已经走过的节点值之后剩余待匹配的值。到叶子时如果 remaining 刚好等于叶子节点值或者你走到叶子后 remaining 减掉叶子值等于 0这就是一条合法路径。为什么用“剩余值”而不是“当前累计值”两者本质等价但剩余值的判断更直观每次递归时执行remaining - node.val到叶子判断remaining node.val或者在进入叶子后判断remaining 0。我个人的习惯是先减去当前节点值再统一判断if not node.left and not node.right and remaining 0。这样三条路径当前、左、右的处理逻辑可以合并代码更简洁。return 值我选择不返回任何东西。既然 result 是共享的可变列表递归过程中往里加结果就行。这个设计在 LeetCode 题解里非常常见面试时也更容易解释。当然你也能改成返回左右子树的路径列表再拼接但那样会产生大量中间列表拷贝性能差很多代码也更绕我建议还是用共享容器。2.2 空节点和叶子判断很多运行时错误的根源先回答那个热搜问题写二叉树程序时为什么总是报运行时错误。绝大多数情况是空节点没判断就访问属性。在路径总和 II 里递归结束条件必须考虑两种情况真实叶子节点和空节点。你如果写成下面这样就会踩坑if node is None: return这行代码虽然简单却至关重要。如果没有它当你调用叶子节点的左孩子时拿到的是 None下一步None.val直接抛AttributeError: NoneType object has no attribute val。这类报错在刷题平台上的出现频率高得惊人。叶子判断也很关键。叶子节点的定义是node.left is None and node.right is None。千万别用“左右孩子有一个为空”或者“当前节点没有孩子”的直觉简化版要用严格的逻辑与。我见过有人把叶子判断写成if not node.left or not node.right这会把只有左孩子没有右孩子的中间节点也当成叶子导致收集到错误的路径。还有一个容易犯的错在remaining 0时直接收集路径但忘了检查当前节点是不是叶子。结果这条路径可能走到一半当前节点下面还有孩子把它提前收进结果集最后和标准答案对不上。正确顺序是先进入节点减掉节点值再同时判断叶子条件和剩余值条件。2.3 回溯动作必须成对出现回溯说穿了就是“递归前选一条分支递归结束后撤销这次选择”。在代码里最直接的表现就是 append 和 pop 成对出现path.append(node.val) dfs(node.left, remaining, path, result) dfs(node.right, remaining, path, result) path.pop()为什么必须在两次递归之后统一 pop而不是在递归到了叶子找到结果后马上 return因为即使找到了合法路径你也不能直接返回父节点你只是完成了左子树的探索父节点可能右子树还有一条合法路径。如果你在找到路径后return而忘记 pop回溯链就断了路径列表里会残留当前叶子的节点值后续兄弟分支的路径会整体错乱。这里我建议你养成一个习惯把 append 和 pop 放在同一个函数作用域里递归调用夹在中间。真正收集结果的时候不要提前 return让递归自然走完最后统一 pop。这种写法虽然稍微牺牲了一点点可读性但能大幅降低漏写 pop 的概率。2.4 收集路径时必须拷贝否则全盘皆输即使你把递归和回溯都写对了还有一个特别隐蔽的坑收集结果时直接result.append(path)。在很多语言里列表是引用类型你 append 进 result 的并不是当前路径的副本而是指向同一个列表对象的引用。等到递归回溯path 里的节点被不断 popresult 中保存的那些路径也会跟着变化。最终你会发现 result 里的每条结果都变成了同一串东西通常还是最后一条路径的残留。解决办法很简单收集时拷贝一份快照result.append(path[:])path[:]是 Python 里常用的浅拷贝写法也可以用list(path)。我印象里至少有两次线下训练营学员在普通递归里都通过样例了一到这个需要收集路径的题就百思不得其解最后查出来就是少了这一下拷贝。这个坑如果你提前知道能省下很多调试时间。3. 完整参考实现递归加回溯以及手推过程3.1 参考代码Python 递归写法下面这段代码是我目前在面试中比较推荐的主写法逻辑直白不容易出错from typing import Optional, List class Solution: def pathSum(self, root: Optional[TreeNode], targetSum: int) - List[List[int]]: result [] if root is None: return result path [] self.dfs(root, targetSum, path, result) return result def dfs(self, node: Optional[TreeNode], remaining: int, path: List[int], result: List[List[int]]) - None: if node is None: return # 进入当前节点尝试加入路径 path.append(node.val) remaining - node.val # 到达叶子节点并且剩余值归零说明当前路径达标 if node.left is None and node.right is None and remaining 0: result.append(path[:]) # 注意这里不 return统一走最后的 pop # 如果提前 return必须在 return 前先 pop # 继续向下探索 self.dfs(node.left, remaining, path, result) self.dfs(node.right, remaining, path, result) # 回溯撤销当前节点的选择 path.pop()这个写法把递归终止条件统一放在函数开头if node is None这一行一次性处理了空子树这样后面访问node.left时一定安全。另外我在叶子判断处刻意不 return让代码最后统一 pop这是我对自己的编码习惯要求回溯动作只在函数出口执行一次避免多条 return 路径导致的漏 pop。如果你对提前 return 更熟练也可以这么写if node.left is None and node.right is None: if remaining 0: result.append(path[:]) path.pop() return但这样必须记住手动 pop代码稍不留神就会漏。我更推荐第一种它把 pop 固定为一个出口函数的结束位置就是回溯的位置。3.2 用题目样例手推一遍递归过程LeetCode 原题的示例二叉树结构如下5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1targetSum 是 22期待输出是[[5, 4, 11, 2], [5, 8, 4, 1]]。我们手动推一遍第一条路径让你感受一下 path 的变化过程。从根节点 5 出发path 变成[5]剩余值 17。先进入左子树 4path 变成[5, 4]剩余值 13。再进入 4 的左孩子 11path 变成[5, 4, 11]剩余值 2。11 的左边是 7path 变成[5, 4, 11, 7]剩余值 -5。7 是叶子节点但剩余值不是 0所以不收集。递归调用返回执行 poppath 变回[5, 4, 11]。接着进入 11 的右孩子 2path 变成[5, 4, 11, 2]剩余值 0并且 2 是叶子节点此时收集path[:]得到[5, 4, 11, 2]。然后继续执行 poppath 依次变回[5, 4, 11]、[5, 4]、[5]再回到根节点 5 这一层开始遍历右子树 8。右子树的路径类似走到 8 的左孩子 13 时剩余值会变成 -813 不是叶子继续向下走它的右孩子13 只有一个右孩子看树结构13 没有左孩子但有右孩子原题里 13 是叶子。我记忆中的示例树13 下面没孩子那么走到 13 时 path 为[5, 8, 13]剩余值 -4不是叶子合法路径回溯。然后走 8 的右孩子 44 的右孩子 1 是叶子path 为[5, 8, 4, 1]剩余值 0收集成功。第二条路径结束。这个手推过程建议你在纸上画一遍尤其是要盯着 path 的 append 和 pop 节奏看。只要画过一次递归树后面做任何回溯题你都会有“弹栈撤销”的画面感。3.3 复杂度分析面试最容易追问的地方很多人以为这题的时间复杂度是 O(N)其实没那么简单。每个节点都会被访问一次遍历部分确实是 O(N)。但结果收集部分每找到一条合法路径你都要拷贝一份长度为路径长度 L 的列表。最极端情况下树很深并且合法路径很多拷贝的总成本会达到 O(N * H)其中 H 是树高。更严谨地说时间复杂度大致是 O(N * H) 量级普通二叉树下 H 是 log N退化链式树时 H 等于 N这时光拷贝路径就很可观。空间复杂度如果不计入最终结果集主要是递归调用栈和 path 列表的开销。递归栈深度是树高 Hpath 列表在最深时也保存 H 个元素所以是 O(H)。这里要注意许多答案里会写 O(N)那是因为考虑最坏情况链式树的树高等于节点数 N通常两种说法面试时都能接受但你得能解释清楚 H 和 N 的关系。4. 写二叉树程序时为什么总是报运行时错误排查实录4.1 高频运行时错误速查表我梳理了一下自己在写路径总和 II 和同类二叉树题目时见过的报错做成一个速查表你下次遇到直接从表里对症状。症状常见原因解决思路NoneTypeobject has no attributeval递归到了空节点但没判断函数开头先if node is None: return收集到的路径内容全变成最后一条路径result.append(path)没有拷贝改写成result.append(path[:])结果里出现非叶子路径只判断 remaining 为 0没判断叶子同时要求node.left is None and node.right is None递归无法结束栈溢出叶子判断或返回条件写错递归无限进行打印 path 和 node.val检查递归终止条件同一路径重复出现在左右子树递归后没统一 pop导致路径重复累计检查 append、pop 是否严格成对运行结果顺序和预期不一致迭代栈写法时入栈顺序反了先 push 右子树再 push 左子树保证左子树先处理这里面最典型的就是第一行空节点。写递归时人总有侥幸心理觉得树只要非空递归过程就不会碰到 None。但叶子节点的孩子一定是 None你只要想递归到叶子以下就必须处理空节点。我自己的习惯是凡是二叉树递归第一行代码永远是判空。4.2 节点值是负数时千万别乱剪枝我知道网上很多路径总和题解会出现类似“若当前剩余值小于 0 就直接剪枝”的优化。这种优化是建立在题目保证节点值为非负数的基础上的。但 LeetCode 113 的题目说明里并没有这个限制节点值可以是正数、负数或 0。也就是说你在某个节点发现剩余值已经是负数不代表后续路径没有希望因为只要再来几个负数总和又可能回到 0。有一次我就见过一个学员在递归里加了一行if remaining 0: return然后拿着样例一测确实能过因为样例里没有负数路径。提交之后隐藏样例立刻报错。这个问题极其隐蔽因为它不是运行时错误而是逻辑错误你少收集了一部分答案系统判定 Wrong Answer。如果你真想基于剩余值做优化至少要确认题目是否默认节点值为正113 这道题没有这个前提所以我建议老老实实遍历完整棵树。4.3 二叉树深度与递归爆栈何时切换到迭代写法二叉树递归写法虽然好懂但有一个天然软肋递归深度受调用栈限制。Python 的默认递归深度限制通常在 1000 左右如果这棵树长得像一根链子节点数接近 1000你的递归就会触发RecursionError: maximum recursion depth exceeded in comparison。这类报错在“二叉树的深度”和“路径总和”相关题目里都常出现。解决办法有两种。第一种是主动调大递归限制import sys sys.setrecursionlimit(10000)这只是给递归争取更大空间治标不治本。第二种更稳妥直接换迭代写法。路径总和 II 的迭代版本也可以用栈模拟 DFS因为每个栈帧里保存独立的路径列表天然不需要显式回溯class Solution: def pathSum(self, root: Optional[TreeNode], targetSum: int) - List[List[int]]: if root is None: return [] result [] stack [(root, targetSum - root.val, [root.val])] while stack: node, remaining, path stack.pop() if node.left is None and node.right is None: if remaining 0: result.append(path) continue if node.left is not None: stack.append((node.left, remaining - node.left.val, path [node.left.val])) if node.right is not None: stack.append((node.right, remaining - node.right.val, path [node.right.val])) return result注意这里path [node.left.val]会产生一个新列表不会影响其他栈帧因此不需要 pop。这种写法的缺点是空间占用更大栈里会保存很多份路径列表优点是不会爆递归栈适合处理极端深度的树。我一般建议面试时先讲递归版本如果面试官追问树特别深怎么办再展示迭代版本。5. 由这道题引出的扩展与面试加分区5.1 从路径总和 II 到路径总和 III起点不再固定LeetCode 还有一道著名的路径总和 III题目变成了路径可以从任意节点出发向下延伸到任意节点只要路径和为 targetSum 就算一条不要求起点是根也不要求终点是叶子。这道题做的过程中你需要外层遍历每一个节点作为起点内层继续向下搜索路径复杂度往往退化到 O(N^2)。更优的做法是借助前缀和加哈希表把路径问题转化成类似“连续子数组和为 k”的计数问题。如果你能把路径总和 II 的回溯思想吃透再看路径总和 III 会有一种“原来是同一个套路”的感觉。它们都要维护一条当前路径只是 III 的路径起点更灵活判断截止点也更自由。很多同学直接做 III 会觉得晕我建议他们先做 113 这道题把“当前路径怎么进怎么出”彻底搞懂再过渡到 III 就顺畅很多。5.2 搜索二叉树BST对这道题没有额外帮助这是不少初学者容易误解的地方。搜索二叉树确实有“左子树所有节点小于根右子树所有节点大于根”的天然约束问题在于路径总和 II 要的是穷举所有满足条件的路径它的判断条件只和节点值的累加有关和节点之间的大小关系无关。换句话说BST 的大小特性帮不了你做剪枝因为你不知道当前节点下面还藏着哪些负数节点更不知道剩余路径累加会变成什么结果。但如果你在面试中遇到“这棵树是 BST”的条件可以主动提一句遍历方向上左子树和右子树可以按 BST 顺序输出结果在当前题目里没有排序要求所以 DFS 顺序无所谓。这种细节会显得你思考全面但不是得分重点。5.3 线索二叉树与 O(1) 空间遍历的讨论线索二叉树的核心思路是利用叶子节点的空指针记录中序遍历下的前驱和后继从而在不使用栈和递归的前提下完成遍历常见的实现就是 Morris 遍历。如果你在面试中聊到“能不能用 O(1) 额外空间遍历二叉树”可以提到 Morris 前序遍历理论上来讲路径总和 II 也能用 Morris 加额外路径记录实现。但注意真正输出路径时你还是需要保存当前路径的快照结果集本身就是要占空间的所以纯的 O(1) 空间在这里意义有限。我的建议是不要把线索二叉树当作这道题的重点。面试官如果问你能接住一两句 Morris 遍历的概念说明你知识面广但如果花大量时间展开细节反而可能冲淡核心技能展示。算法面试考察的核心是你会不会分析递归与回溯而不是你会不会默写 Morris。5.4 面试中如何把这段代码讲得有条理如果你正在准备面试我可以给你一个讲题模板。第一句先说思路“这道题本质上是二叉树前序遍历加回溯。我维护一个路径列表进入节点时加入当前值离开节点时弹出当前值到叶子节点检查剩余值是否为零。” 第二句说关键细节“收集结果时要拷贝当前路径避免后续 pop 污染结果。” 第三句主动说复杂度“时间复杂度 O(N * H)空间复杂度 O(H)H 是树高最坏情况下二者都趋近 O(N)。” 这三句说完你的回答已经覆盖了解题思路、实现细节、复杂度分析三个主要方面非常加分。6. 写在最后关于回溯我的一点刷题体会我最早刷这道题时连续两次栽在同一个坑上收集结果时没有拷贝 path。当时我打印 result 才发现保存下来的所有路径最后都变成了同一串那一刻真的哭笑不得。后来我养成了一个习惯凡是递归里用 list 记录状态就默认要回答两个问题这个 list 什么时候变长什么时候变短收集结果时到底拷贝了没有。这两个问题想清楚回溯题的代码基本不会出大问题。另一个特别实用的习惯是慢一点不要迷信“一下子写出整题代码”。第一遍刷的时候我建议你拿一道非常小的样例比如只有三个节点的树自己在稿纸上画出递归树把每个节点的进入、退出和 path 内容变化全部写下来。这个过程花不了十分钟但对理解回溯的帮助极大。网上教程写得再好都不如你自己手推一遍来得踏实。关于二叉树题目里的运行时错误我也想说两句。绝大多数报错并不可怕它们只是编译器在提醒你边界没处理好。路径总和 II 这道题恰恰能帮你把这些边界问题一次性暴露出来空指针、叶子判断、路径拷贝、递归深度每一个都是后续刷树题的老朋友。如果你现在正卡在这道题上别急把它当成一个查漏补缺的机会把上面每个小节提到的坑都过一遍再回头看代码你会发现思路清楚了很多。