LeetCode 113路径总和II：DFS回溯+切片快照避坑指南

LeetCode 113这道题，估计是很多人第一次真正感受到“回溯”这两个字的分量。单看名字——路径总和 II，它是112题的加强版：112只问你“有没有这么一条从根到叶子的路径”，113却要你把所有满足条件的路径全部列出来。同样的二叉树，同样的DFS遍历，难度一下子从“会递归就能写”跳到了“递归之外还得处理好数据收集”。我见过太多人在这一题上栽跟头，不是思路不通，而是代码跑起来总报运行时错误，或者答案里出现莫名其妙的重复路径、空路径。今天就从这道题出发，把路径总和这类二叉树题型的套路、代码细节、常见报错一锅端清楚。

1. 先别急着写代码：这道题到底在问什么

拿到题目，第一步永远是确认边界和输出要求。113题的标准描述是：给定一棵二叉树的根节点root和一个整数目标和targetSum，找出所有从根节点到叶子节点路径中和等于targetSum的路径，以二维数组形式返回。注意几个关键词：“根节点”“叶子节点”“所有”“路径”。

1.1 和112题的核心差异

112题只需要返回一个布尔值，所以递归到叶子节点时，只要判断当前累加和是否等于目标值，等于就直接返回true，可以提前终止。113题不同，它要求收集所有路径，意味着你不能提前结束，必须完整地遍历整棵树，把符合条件的路径一条条存下来。

这个差异直接决定了代码结构。112题的递归函数可以写成带返回值的类型，碰到满足条件的路径就层层返回true；113题的递归函数更适合写成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 result

Python版本思路完全一致，关键就在result.append(path[:])这行。:切片操作会生成一个新的列表对象，如果你图省事直接写result.append(path)，结果后患无穷——后面每次path.pop()都会同步修改列表，最终result里存的路径全变成空或者同一个末尾状态。

这个坑真的非常隐蔽。我第一次用Python写这题时，输出结果全是空列表，排查了很久才发现是引用共享的问题。记住一条铁律：凡是递归里复用的可变容器，存入最终结果时必须做一层拷贝。

3.3 三种回溯写法的取舍

关于回溯弹出操作，我看到过三种写法。

第一种是我上面展示的：叶子结算后不return，让代码自然走到最后的path = path[:len(path)-1]。这种写法最简单，因为回溯逻辑只有一份，不会遗漏。

第二种是在叶子结算后手动pop再return：

if 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一次就对应一次pop，path不会出现负数长度；但如果你在某些分支提前return却忘了pop，或者在错误位置执行pop，就可能把path弹空。

更普遍的“答案错误”则来自引用污染：递归过程中path是全局复用的切片，你把它存入result后，后续的pop和append会修改它。前面Go里的copy、Python里的path[:]，都是用来做快照的，这一步省不得。我见过太多次“为什么我存进result的路径全是最后一条”的提问，原因百分百是没有做快照。

4.4 常见错误速查表

5. 从“路径总和 II”到一类路径问题的套路

做题不能只做一道题，一道经典题背后往往是一类题。113题学透之后，二叉树路径相关的好几道题都可以用同一套模板拿下。

5.1 一套模板吃透112/113/257

112题，只要判断存在性，把回溯收集的代码去掉，换成一个布尔返回值就够了。

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 的另一种问法。此时你需要在“备份整条路径”和“只维护一个计数器”之间做选择，显然计数器更省空间。理解每个变体在改什么，比背下一百道题的答案重要得多。

最后再说一个实际经验：写二叉树递归代码，我从一开始就把五个部分写整齐，空值判断、进入节点、叶子处理、递归子节点、退出回溯，每次只在这五个槽位里做增删。这个方法让我少踩了无数坑。你拿到任何一道二叉树路径题，都先往这五个槽位里套，先跑通再优化——保证能少走很多弯路。