LeetCode 113这道题估计是很多人第一次真正感受到“回溯”这两个字的分量。单看名字——路径总和 II它是112题的加强版112只问你“有没有这么一条从根到叶子的路径”113却要你把所有满足条件的路径全部列出来。同样的二叉树同样的DFS遍历难度一下子从“会递归就能写”跳到了“递归之外还得处理好数据收集”。我见过太多人在这一题上栽跟头不是思路不通而是代码跑起来总报运行时错误或者答案里出现莫名其妙的重复路径、空路径。今天就从这道题出发把路径总和这类二叉树题型的套路、代码细节、常见报错一锅端清楚。1. 先别急着写代码这道题到底在问什么拿到题目第一步永远是确认边界和输出要求。113题的标准描述是给定一棵二叉树的根节点root和一个整数目标和targetSum找出所有从根节点到叶子节点路径中和等于targetSum的路径以二维数组形式返回。注意几个关键词“根节点”“叶子节点”“所有”“路径”。1.1 和112题的核心差异112题只需要返回一个布尔值所以递归到叶子节点时只要判断当前累加和是否等于目标值等于就直接返回true可以提前终止。113题不同它要求收集所有路径意味着你不能提前结束必须完整地遍历整棵树把符合条件的路径一条条存下来。这个差异直接决定了代码结构。112题的递归函数可以写成带返回值的类型碰到满足条件的路径就层层返回true113题的递归函数更适合写成void——用单个共享的“当前路径”变量配合递归到达叶子节点时判断并保存快照。这里就埋下了第一个经典坑如果你照着112题的写法去改很容易在递归返回值上绕晕或者把路径收集逻辑放错位置。1.2 “路径”的定义与隐含条件“从根节点到叶子节点”这句话比看起来要严格得多。叶子节点的定义是左右孩子都为空的节点。所以路径的终点必须是叶子不能是空节点也不能是只有一边孩子的节点。很多初学者在写递归时喜欢用node nil作为递归出口然后在出口处判断累积和是否等于目标值。这在某些路径题目里可行但放在113题就是错上加错——因为一棵树上会有大量空节点如果拿空节点作为“路径终点”来结算那么“只有一个左孩子的节点”会在它的右孩子为空时被错误地当成一条合法路径的终点。结果就是答案里多出一堆根本没走到叶子的路径。正确的做法是递归进入节点后先检查它是不是叶子也就是node.Left nil node.Right nil。只有在这种情况下才判断路径和才决定是否收集。递归左右孩子之前不能提前结算。2. 算法选型为什么DFS而不是BFS路径总和 II 的核心是“根到叶子”这个结构天然和深度优先遍历DFS绑定。但很多面试官会追问一句BFS行不行当然行但不是一个好方案里面藏着空间开销和代码复杂度两个大问题。2.1 前序遍历与路径天然契合前序遍历的顺序是先访问当前节点再访问左子树再访问右子树。这意味着递归调用进入某个节点时栈帧上已经保存了从根节点到该节点的完整祖先链条。只要在递归过程中用一个全局切片把经过的节点值记录下来当递归到达叶子时这个切片里的内容恰好就是当前路径的完整内容。对比BFS它是按层推进的每个节点只知道自己的父节点是谁并不知道“从根到自己”经过哪些节点。你要想拿到完整路径有两种方案一是每个节点都存储一份从根到自己的路径副本那空间开销直接变成O(N*H)二是在树中保存父指针等找到叶子后再逆向组装路径这样增加了编码复杂度。无论哪种都比不上DFS天然持有路径来得清爽。2.2 减法设计背后的直觉路径和的计算可以有两种视角一种是从根往下累加到叶子时判断累加值是否等于targetSum另一种是从目标值往下减到达叶子时判断剩余值是否为0。两种写法数学上完全等价但我在面试中强烈建议用减法。原因有两个。第一减法的“剩余值”语义更直观每个递归里我只关心“从这个节点往下走还需要凑出多少”。第二后面的扩展题比如路径总和 III用的就是前缀和差值思路习惯减法写法之后理解进阶题会顺畅很多。具体实现就是递归携带一个remain参数当前节点值非空时执行remain - node.Val在叶子处判断remain 0即可。2.3 节点值为负带来的影响我起初也犯过这个错写了“当前路径和超过目标就剪枝”的逻辑结果提交时发现漏掉了很多答案。原因很简单题目并没有说节点值一定为正。一旦树里存在负数当前路径和暂时超过targetSum不代表后面不能靠负值回拉。这就是为什么113题的标准解法里不能做“和大于目标就提前返回”的剪枝。只有当你明确题目给了“所有节点值非负”的约束时才能加这种优化。面试时主动指出这一点反而能体现你对边界条件的敏感度。3. 完整实现核心代码与切片大坑这道题的主流语言写法大同小异核心模块是递归函数 全局结果数组 当前路径数组。下面给出Go版本因为我发现不少读者在Go的切片语义上吃过亏。3.1 Go版本实现与逐行解读func pathSum(root *TreeNode, targetSum int) [][]int { result : make([][]int, 0) path : make([]int, 0) var dfs func(node *TreeNode, remain int) dfs func(node *TreeNode, remain int) { if node nil { return } remain - node.Val path append(path, node.Val) if node.Left nil node.Right nil remain 0 { snapshot : make([]int, len(path)) copy(snapshot, path) result append(result, snapshot) } dfs(node.Left, remain) dfs(node.Right, remain) path path[:len(path)-1] } dfs(root, targetSum) return result }逐行说。递归第一个判断node nil是空指针保护也是递归退出条件。然后remain - node.Val更新剩余目标值path append(path, node.Val)把当前节点值加入路径。关键在叶子结算只有左右孩子都为空并且remain 0时才把当前路径复制一份存入结果。重点是你不能直接append(result, path)而是先make一个新切片用copy把path的内容拷贝进去。这一步就是“路径快照”防止后续回溯时修改path影响已存入的结果。最后递归完左子树和右子树后执行path path[:len(path)-1]把当前节点从路径末尾弹出。这一步叫回溯它的作用是让path恢复到进入当前节点之前的状态这样递归返回上一层时路径内容才不会被污染。3.2 Python版本与“路径快照”的坑class Solution: def pathSum(self, root: Optional[TreeNode], targetSum: int) - List[List[int]]: result [] path [] def dfs(node: Optional[TreeNode], remain: int): if not node: return remain - node.val path.append(node.val) if not node.left and not node.right and remain 0: result.append(path[:]) dfs(node.left, remain) dfs(node.right, remain) path.pop() dfs(root, targetSum) return resultPython版本思路完全一致关键就在result.append(path[:])这行。:切片操作会生成一个新的列表对象如果你图省事直接写result.append(path)结果后患无穷——后面每次path.pop()都会同步修改列表最终result里存的路径全变成空或者同一个末尾状态。这个坑真的非常隐蔽。我第一次用Python写这题时输出结果全是空列表排查了很久才发现是引用共享的问题。记住一条铁律凡是递归里复用的可变容器存入最终结果时必须做一层拷贝。3.3 三种回溯写法的取舍关于回溯弹出操作我看到过三种写法。第一种是我上面展示的叶子结算后不return让代码自然走到最后的path path[:len(path)-1]。这种写法最简单因为回溯逻辑只有一份不会遗漏。第二种是在叶子结算后手动pop再returnif node.Left nil node.Right nil remain 0 { tmp : make([]int, len(path)) copy(tmp, path) result append(result, tmp) path path[:len(path)-1] return }这种写法在逻辑上没问题但要求你在“叶子”和“非叶子”两种情况下都要记得保证路径弹出——叶子分支弹出后立即返回普通节点继续递归。代码里出现两个回溯点一旦后续需求变化就容易漏改。第三种是我明确不推荐的用空节点作为结算点在node nil时判断remain 0并收集路径。如前文所说这种写法会收集到大量到达空节点的“半路径”而这些路径根本没有走到真正的叶子。除非你额外维护深度信息并做叶子判断否则不要用。我自己一直用第一种因为回溯只写一次心智负担最小也最不容易在“提交后才发现多了或少了路径”这种问题上翻车。3.4 复杂度到底怎么算复杂度是面试必问。假设二叉树有N个节点高度为H。时间上每个节点都会被访问一次这是O(N)每当遇到一个叶子且路径合法时需要拷贝长度为H的路径拷贝是O(H)。叶子数量最多为N所以最坏时间复杂度是O(N*H)。对于完全二叉树H logN复杂度就可以写成O(N*logN)对于极端斜树H N耗时退化为O(N^2)。空间上要分两部分看。不考虑结果存储时递归栈深度为O(H)路径数组长度也是O(H)所以临时空间是O(H)加上最终结果数组里存了所有路径总共O(L*H)L是合法路径数量。很多题解只写O(N)严格来说不准确面试时可以更严谨地拆分说明。4. 写二叉树程序为什么总报运行时错误我翻了大量二叉树相关的代码求助帖发现运行时错误高频集中在空指针、栈溢出、数组越界、引用污染这几类。113题恰好能把这些问题全部暴露出来。4.1 空指针九成运行时错误都长这样最经典的报错就是panic: runtime error: invalid memory address or nil pointer dereference展开后往往指向node.Left.Val或者node.Right.Val这一类访问。为什么二叉树代码里空指针这么多因为很多人在递归里只想着处理“当前节点”却忘了当前节点可能已经是nil。在113题里我在递归入口先判断if node nil { return }就是避免后续访问node.Val或node.Left时崩溃。另一个容易忽略的场景是如果你用了node.Left nil node.Right nil来判断叶子那么在判断之前node本身必须已经保证非空。这也是为什么空指针判断必须在叶子判断之前。日常写树代码时我建议形成肌肉记忆任何函数体里用到node.xxx之前先确认node不可能为空递归入口处第一行写空值返回是最稳妥的模式。4.2 递归栈溢出与极端树形很多人跑二叉树代码时遇到栈溢出第一反应是“代码写错了”其实有时候是测试数据的形态太极端。如果一棵树退化成了链表形态比如每个节点只有右孩子那么递归深度等于节点数量。当节点数量达到十万级别时函数调用栈会被打穿程序直接崩溃。应对方式有两种。一是面试和笔试场景下默认测试数据不会极端到爆栈但你要有这个意识二是真正处理超大深度树时改用迭代写法用显式栈存储(node, remain)和当前路径索引出栈时执行回溯。这种写法比递归繁琐但可控性更强。另外一个特别小的建议本地自测时千万别把树的左右指针手动互指成环否则递归将无限循环直接内存溢出。这是我见过最尴尬的“运行时错误”。4.3 切片越界和引用污染113题里还有一个非常隐蔽的运行时错误path path[:len(path)-1]在path为空切片时执行会触发切片越界。什么情况下path会是空的如果你用我推荐的递归写法每次append一次就对应一次poppath不会出现负数长度但如果你在某些分支提前return却忘了pop或者在错误位置执行pop就可能把path弹空。更普遍的“答案错误”则来自引用污染递归过程中path是全局复用的切片你把它存入result后后续的pop和append会修改它。前面Go里的copy、Python里的path[:]都是用来做快照的这一步省不得。我见过太多次“为什么我存进result的路径全是最后一条”的提问原因百分百是没有做快照。4.4 常见错误速查表症状可能原因解决方案nil pointer dereference访问了空节点的字段递归入口先判断node nil结果里多出非叶子路径用空节点作为结算点叶子判断必须用Left nil Right nil结果为空列表把未拷贝的path直接入结果Go用copyPython用path[:]路径内容全是最后一条引用了同一个底层数组每次保存结果做一次快照栈溢出/内存溢出树退化成链表 或 树中存在环改用迭代栈自测时避免成环slice bounds out of rangepath被提前弹出或重复弹出保证append和pop一一对应5. 从“路径总和 II”到一类路径问题的套路做题不能只做一道题一道经典题背后往往是一类题。113题学透之后二叉树路径相关的好几道题都可以用同一套模板拿下。5.1 一套模板吃透112/113/257112题只要判断存在性把回溯收集的代码去掉换成一个布尔返回值就够了。func hasPathSum(root *TreeNode, targetSum int) bool { if root nil { return false } targetSum - root.Val if root.Left nil root.Right nil { return targetSum 0 } return hasPathSum(root.Left, targetSum) || hasPathSum(root.Right, targetSum) }257题求所有从根到叶子的路径不要求和可以理解为113题的简化版去掉remain参数和数值判断只剩路径拼接。更关键的是这三道题的骨架完全一致递归入口空值检查、进入节点后把值加入路径、叶子节点处理、递归左右子树、退出时弹出路径。把这五个部分背下来路径类题目就稳了。5.2 扩展路径总和III与前缀和经常有人问路径总和 III 为什么不能直接套113的模板因为III的路径起点不再限定是根节点也不再限定终点必须是叶子。要用113的DFS思路去做就得对每个节点都发起一次DFS复杂度达到O(N^2)在节点数上万时明显吃力。更优的做法是前缀和加哈希表在DFS过程中维护从根到当前节点的累加和每个节点处去查“当前和减去targetSum”在前缀和表中出现过几次这个出现次数就是符合要求的路径条数。理解这个优化之后回头再看113你会发现在DFS遍历过程中维护“消耗值”和“路径状态”本质上是一脉相承的。5.3 面试官可能追着问的变体聊到路径总和系列面试官大概率会追问几个变体如果树是二叉搜索树BST能不能利用节点值有序性剪枝如果BST且所有节点值为正可以在remain 0时剪掉整棵子树因为往任何子节点走都会让剩余值更小。但普通二叉树不能这样剪因为负值存在。另一个冷门变体是线索二叉树。这个数据结构是为了把遍历过程的空间复杂度降到O(1)实现“不用递归也不用显式栈”的遍历。但对于路径总和这类需要动态回溯的题目线索二叉树的收益很低因为每次回溯仍然需要额外记录状态构建线索本身也要改动树结构。面试时提到你能想到线索二叉树说明对遍历优化的边界有认知但实际解答还是用普通DFS更务实。还有一类反向变体不要求返回路径内容只要求统计满足条件的路径数量这就是路径总和 III 的另一种问法。此时你需要在“备份整条路径”和“只维护一个计数器”之间做选择显然计数器更省空间。理解每个变体在改什么比背下一百道题的答案重要得多。最后再说一个实际经验写二叉树递归代码我从一开始就把五个部分写整齐空值判断、进入节点、叶子处理、递归子节点、退出回溯每次只在这五个槽位里做增删。这个方法让我少踩了无数坑。你拿到任何一道二叉树路径题都先往这五个槽位里套先跑通再优化——保证能少走很多弯路。 LeetCode 113路径总和II：DFS回溯+切片快照避坑指南
LeetCode 113这道题估计是很多人第一次真正感受到“回溯”这两个字的分量。单看名字——路径总和 II它是112题的加强版112只问你“有没有这么一条从根到叶子的路径”113却要你把所有满足条件的路径全部列出来。同样的二叉树同样的DFS遍历难度一下子从“会递归就能写”跳到了“递归之外还得处理好数据收集”。我见过太多人在这一题上栽跟头不是思路不通而是代码跑起来总报运行时错误或者答案里出现莫名其妙的重复路径、空路径。今天就从这道题出发把路径总和这类二叉树题型的套路、代码细节、常见报错一锅端清楚。1. 先别急着写代码这道题到底在问什么拿到题目第一步永远是确认边界和输出要求。113题的标准描述是给定一棵二叉树的根节点root和一个整数目标和targetSum找出所有从根节点到叶子节点路径中和等于targetSum的路径以二维数组形式返回。注意几个关键词“根节点”“叶子节点”“所有”“路径”。1.1 和112题的核心差异112题只需要返回一个布尔值所以递归到叶子节点时只要判断当前累加和是否等于目标值等于就直接返回true可以提前终止。113题不同它要求收集所有路径意味着你不能提前结束必须完整地遍历整棵树把符合条件的路径一条条存下来。这个差异直接决定了代码结构。112题的递归函数可以写成带返回值的类型碰到满足条件的路径就层层返回true113题的递归函数更适合写成void——用单个共享的“当前路径”变量配合递归到达叶子节点时判断并保存快照。这里就埋下了第一个经典坑如果你照着112题的写法去改很容易在递归返回值上绕晕或者把路径收集逻辑放错位置。1.2 “路径”的定义与隐含条件“从根节点到叶子节点”这句话比看起来要严格得多。叶子节点的定义是左右孩子都为空的节点。所以路径的终点必须是叶子不能是空节点也不能是只有一边孩子的节点。很多初学者在写递归时喜欢用node nil作为递归出口然后在出口处判断累积和是否等于目标值。这在某些路径题目里可行但放在113题就是错上加错——因为一棵树上会有大量空节点如果拿空节点作为“路径终点”来结算那么“只有一个左孩子的节点”会在它的右孩子为空时被错误地当成一条合法路径的终点。结果就是答案里多出一堆根本没走到叶子的路径。正确的做法是递归进入节点后先检查它是不是叶子也就是node.Left nil node.Right nil。只有在这种情况下才判断路径和才决定是否收集。递归左右孩子之前不能提前结算。2. 算法选型为什么DFS而不是BFS路径总和 II 的核心是“根到叶子”这个结构天然和深度优先遍历DFS绑定。但很多面试官会追问一句BFS行不行当然行但不是一个好方案里面藏着空间开销和代码复杂度两个大问题。2.1 前序遍历与路径天然契合前序遍历的顺序是先访问当前节点再访问左子树再访问右子树。这意味着递归调用进入某个节点时栈帧上已经保存了从根节点到该节点的完整祖先链条。只要在递归过程中用一个全局切片把经过的节点值记录下来当递归到达叶子时这个切片里的内容恰好就是当前路径的完整内容。对比BFS它是按层推进的每个节点只知道自己的父节点是谁并不知道“从根到自己”经过哪些节点。你要想拿到完整路径有两种方案一是每个节点都存储一份从根到自己的路径副本那空间开销直接变成O(N*H)二是在树中保存父指针等找到叶子后再逆向组装路径这样增加了编码复杂度。无论哪种都比不上DFS天然持有路径来得清爽。2.2 减法设计背后的直觉路径和的计算可以有两种视角一种是从根往下累加到叶子时判断累加值是否等于targetSum另一种是从目标值往下减到达叶子时判断剩余值是否为0。两种写法数学上完全等价但我在面试中强烈建议用减法。原因有两个。第一减法的“剩余值”语义更直观每个递归里我只关心“从这个节点往下走还需要凑出多少”。第二后面的扩展题比如路径总和 III用的就是前缀和差值思路习惯减法写法之后理解进阶题会顺畅很多。具体实现就是递归携带一个remain参数当前节点值非空时执行remain - node.Val在叶子处判断remain 0即可。2.3 节点值为负带来的影响我起初也犯过这个错写了“当前路径和超过目标就剪枝”的逻辑结果提交时发现漏掉了很多答案。原因很简单题目并没有说节点值一定为正。一旦树里存在负数当前路径和暂时超过targetSum不代表后面不能靠负值回拉。这就是为什么113题的标准解法里不能做“和大于目标就提前返回”的剪枝。只有当你明确题目给了“所有节点值非负”的约束时才能加这种优化。面试时主动指出这一点反而能体现你对边界条件的敏感度。3. 完整实现核心代码与切片大坑这道题的主流语言写法大同小异核心模块是递归函数 全局结果数组 当前路径数组。下面给出Go版本因为我发现不少读者在Go的切片语义上吃过亏。3.1 Go版本实现与逐行解读func pathSum(root *TreeNode, targetSum int) [][]int { result : make([][]int, 0) path : make([]int, 0) var dfs func(node *TreeNode, remain int) dfs func(node *TreeNode, remain int) { if node nil { return } remain - node.Val path append(path, node.Val) if node.Left nil node.Right nil remain 0 { snapshot : make([]int, len(path)) copy(snapshot, path) result append(result, snapshot) } dfs(node.Left, remain) dfs(node.Right, remain) path path[:len(path)-1] } dfs(root, targetSum) return result }逐行说。递归第一个判断node nil是空指针保护也是递归退出条件。然后remain - node.Val更新剩余目标值path append(path, node.Val)把当前节点值加入路径。关键在叶子结算只有左右孩子都为空并且remain 0时才把当前路径复制一份存入结果。重点是你不能直接append(result, path)而是先make一个新切片用copy把path的内容拷贝进去。这一步就是“路径快照”防止后续回溯时修改path影响已存入的结果。最后递归完左子树和右子树后执行path path[:len(path)-1]把当前节点从路径末尾弹出。这一步叫回溯它的作用是让path恢复到进入当前节点之前的状态这样递归返回上一层时路径内容才不会被污染。3.2 Python版本与“路径快照”的坑class Solution: def pathSum(self, root: Optional[TreeNode], targetSum: int) - List[List[int]]: result [] path [] def dfs(node: Optional[TreeNode], remain: int): if not node: return remain - node.val path.append(node.val) if not node.left and not node.right and remain 0: result.append(path[:]) dfs(node.left, remain) dfs(node.right, remain) path.pop() dfs(root, targetSum) return resultPython版本思路完全一致关键就在result.append(path[:])这行。:切片操作会生成一个新的列表对象如果你图省事直接写result.append(path)结果后患无穷——后面每次path.pop()都会同步修改列表最终result里存的路径全变成空或者同一个末尾状态。这个坑真的非常隐蔽。我第一次用Python写这题时输出结果全是空列表排查了很久才发现是引用共享的问题。记住一条铁律凡是递归里复用的可变容器存入最终结果时必须做一层拷贝。3.3 三种回溯写法的取舍关于回溯弹出操作我看到过三种写法。第一种是我上面展示的叶子结算后不return让代码自然走到最后的path path[:len(path)-1]。这种写法最简单因为回溯逻辑只有一份不会遗漏。第二种是在叶子结算后手动pop再returnif node.Left nil node.Right nil remain 0 { tmp : make([]int, len(path)) copy(tmp, path) result append(result, tmp) path path[:len(path)-1] return }这种写法在逻辑上没问题但要求你在“叶子”和“非叶子”两种情况下都要记得保证路径弹出——叶子分支弹出后立即返回普通节点继续递归。代码里出现两个回溯点一旦后续需求变化就容易漏改。第三种是我明确不推荐的用空节点作为结算点在node nil时判断remain 0并收集路径。如前文所说这种写法会收集到大量到达空节点的“半路径”而这些路径根本没有走到真正的叶子。除非你额外维护深度信息并做叶子判断否则不要用。我自己一直用第一种因为回溯只写一次心智负担最小也最不容易在“提交后才发现多了或少了路径”这种问题上翻车。3.4 复杂度到底怎么算复杂度是面试必问。假设二叉树有N个节点高度为H。时间上每个节点都会被访问一次这是O(N)每当遇到一个叶子且路径合法时需要拷贝长度为H的路径拷贝是O(H)。叶子数量最多为N所以最坏时间复杂度是O(N*H)。对于完全二叉树H logN复杂度就可以写成O(N*logN)对于极端斜树H N耗时退化为O(N^2)。空间上要分两部分看。不考虑结果存储时递归栈深度为O(H)路径数组长度也是O(H)所以临时空间是O(H)加上最终结果数组里存了所有路径总共O(L*H)L是合法路径数量。很多题解只写O(N)严格来说不准确面试时可以更严谨地拆分说明。4. 写二叉树程序为什么总报运行时错误我翻了大量二叉树相关的代码求助帖发现运行时错误高频集中在空指针、栈溢出、数组越界、引用污染这几类。113题恰好能把这些问题全部暴露出来。4.1 空指针九成运行时错误都长这样最经典的报错就是panic: runtime error: invalid memory address or nil pointer dereference展开后往往指向node.Left.Val或者node.Right.Val这一类访问。为什么二叉树代码里空指针这么多因为很多人在递归里只想着处理“当前节点”却忘了当前节点可能已经是nil。在113题里我在递归入口先判断if node nil { return }就是避免后续访问node.Val或node.Left时崩溃。另一个容易忽略的场景是如果你用了node.Left nil node.Right nil来判断叶子那么在判断之前node本身必须已经保证非空。这也是为什么空指针判断必须在叶子判断之前。日常写树代码时我建议形成肌肉记忆任何函数体里用到node.xxx之前先确认node不可能为空递归入口处第一行写空值返回是最稳妥的模式。4.2 递归栈溢出与极端树形很多人跑二叉树代码时遇到栈溢出第一反应是“代码写错了”其实有时候是测试数据的形态太极端。如果一棵树退化成了链表形态比如每个节点只有右孩子那么递归深度等于节点数量。当节点数量达到十万级别时函数调用栈会被打穿程序直接崩溃。应对方式有两种。一是面试和笔试场景下默认测试数据不会极端到爆栈但你要有这个意识二是真正处理超大深度树时改用迭代写法用显式栈存储(node, remain)和当前路径索引出栈时执行回溯。这种写法比递归繁琐但可控性更强。另外一个特别小的建议本地自测时千万别把树的左右指针手动互指成环否则递归将无限循环直接内存溢出。这是我见过最尴尬的“运行时错误”。4.3 切片越界和引用污染113题里还有一个非常隐蔽的运行时错误path path[:len(path)-1]在path为空切片时执行会触发切片越界。什么情况下path会是空的如果你用我推荐的递归写法每次append一次就对应一次poppath不会出现负数长度但如果你在某些分支提前return却忘了pop或者在错误位置执行pop就可能把path弹空。更普遍的“答案错误”则来自引用污染递归过程中path是全局复用的切片你把它存入result后后续的pop和append会修改它。前面Go里的copy、Python里的path[:]都是用来做快照的这一步省不得。我见过太多次“为什么我存进result的路径全是最后一条”的提问原因百分百是没有做快照。4.4 常见错误速查表症状可能原因解决方案nil pointer dereference访问了空节点的字段递归入口先判断node nil结果里多出非叶子路径用空节点作为结算点叶子判断必须用Left nil Right nil结果为空列表把未拷贝的path直接入结果Go用copyPython用path[:]路径内容全是最后一条引用了同一个底层数组每次保存结果做一次快照栈溢出/内存溢出树退化成链表 或 树中存在环改用迭代栈自测时避免成环slice bounds out of rangepath被提前弹出或重复弹出保证append和pop一一对应5. 从“路径总和 II”到一类路径问题的套路做题不能只做一道题一道经典题背后往往是一类题。113题学透之后二叉树路径相关的好几道题都可以用同一套模板拿下。5.1 一套模板吃透112/113/257112题只要判断存在性把回溯收集的代码去掉换成一个布尔返回值就够了。func hasPathSum(root *TreeNode, targetSum int) bool { if root nil { return false } targetSum - root.Val if root.Left nil root.Right nil { return targetSum 0 } return hasPathSum(root.Left, targetSum) || hasPathSum(root.Right, targetSum) }257题求所有从根到叶子的路径不要求和可以理解为113题的简化版去掉remain参数和数值判断只剩路径拼接。更关键的是这三道题的骨架完全一致递归入口空值检查、进入节点后把值加入路径、叶子节点处理、递归左右子树、退出时弹出路径。把这五个部分背下来路径类题目就稳了。5.2 扩展路径总和III与前缀和经常有人问路径总和 III 为什么不能直接套113的模板因为III的路径起点不再限定是根节点也不再限定终点必须是叶子。要用113的DFS思路去做就得对每个节点都发起一次DFS复杂度达到O(N^2)在节点数上万时明显吃力。更优的做法是前缀和加哈希表在DFS过程中维护从根到当前节点的累加和每个节点处去查“当前和减去targetSum”在前缀和表中出现过几次这个出现次数就是符合要求的路径条数。理解这个优化之后回头再看113你会发现在DFS遍历过程中维护“消耗值”和“路径状态”本质上是一脉相承的。5.3 面试官可能追着问的变体聊到路径总和系列面试官大概率会追问几个变体如果树是二叉搜索树BST能不能利用节点值有序性剪枝如果BST且所有节点值为正可以在remain 0时剪掉整棵子树因为往任何子节点走都会让剩余值更小。但普通二叉树不能这样剪因为负值存在。另一个冷门变体是线索二叉树。这个数据结构是为了把遍历过程的空间复杂度降到O(1)实现“不用递归也不用显式栈”的遍历。但对于路径总和这类需要动态回溯的题目线索二叉树的收益很低因为每次回溯仍然需要额外记录状态构建线索本身也要改动树结构。面试时提到你能想到线索二叉树说明对遍历优化的边界有认知但实际解答还是用普通DFS更务实。还有一类反向变体不要求返回路径内容只要求统计满足条件的路径数量这就是路径总和 III 的另一种问法。此时你需要在“备份整条路径”和“只维护一个计数器”之间做选择显然计数器更省空间。理解每个变体在改什么比背下一百道题的答案重要得多。最后再说一个实际经验写二叉树递归代码我从一开始就把五个部分写整齐空值判断、进入节点、叶子处理、递归子节点、退出回溯每次只在这五个槽位里做增删。这个方法让我少踩了无数坑。你拿到任何一道二叉树路径题都先往这五个槽位里套先跑通再优化——保证能少走很多弯路。