企业官网建设流程全解析

刷二叉树算法题，很多人有个共同感受：遍历、翻转、求深度这类题只能算热身，一旦碰到“路径”两个字，难度立刻上一个台阶。今天要拆解的这道“二叉树中和为某一值的路径”，正是路径题里最经典的入门款，它同时考察递归、回溯、状态拷贝这一整套基本功，也是很多人在二叉树阶段第一次感觉到“看答案能看懂，自己写就漏细节”的题目。

题面其实很简单：输入一棵二叉树和一个整数，要求输出所有从根节点到叶子节点的路径，并且路径上节点值的总和刚好等于这个整数。注意“路径”不是任意节点连通路径，必须是“根到叶子”，这个定义直接决定了后面所有写法。它适合两类读者：一是刚学完二叉树遍历、想进一步理解递归回溯的进阶者，二是在准备算法面试、需要把经典题真正吃透而不是背答案的系统刷题人。

这篇文章会把完整推导、标准实现、复杂度和高频踩坑全部讲透，代码以 Python 为主，同时给出 Java 和 JavaScript 的关键差异，方便你用自己熟悉的语言直接照搬落地。

1. 题面拆解：路径必须是从根到叶才算数

1.1 先给一棵小树，把答案人工算出来

在写代码之前，我强烈建议先把路径“肉眼数一遍”。就拿下面这棵树来说：

5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1

假设目标值 target = 22，那么符合条件的所有根到叶路径是两条：

5 -> 4 -> 11 -> 2 （总和 22） 5 -> 8 -> 4 -> 5 （总和 22）

为什么不是5 -> 8 -> 13？因为 13 虽然走到头了，但总和是 26，不等于 22。为什么不是5 -> 8 -> 4 -> 1？虽然也是从根到叶子，但总和是 18，也不符合。这个“先手工枚举一遍”的动作，是一个很有效的自查习惯：代码写完跑出来的答案，和手算结果对不上，说明递归逻辑里肯定埋着问题。

1.2 递归解法为什么是首选

树本身就是一种递归定义的数据结构：一个节点由值和左右子树组成，而左右子树依然是树。因此“从某个节点出发找根到叶路径”这个问题，天然可以被分解为“把当前节点加入路径，然后在左右子树中继续寻找剩余部分”。这种自上而下的递推关系，和递归的实现方式是完全匹配的。

如果不用递归，就需要自己维护栈去模拟函数调用过程，还要在栈里额外保存当前节点、当前路径和当前累计值，代码会明显更啰嗦，而且调试起来极不直观。递归版本把调用栈交给系统维护，代码量和人类思维习惯高度一致，所以在算法面试里，这道题几乎都是默认用递归来解。

这个解法里最重要的两个关键词，一个是“递归”，另一个是“回溯”。递归负责深入子树，回溯负责在返回时把路径状态恢复到进入分支之前的状态，两者必须配合使用。这也是整个题目的核心难点所在。

1.3 动手前先把边界条件想清楚

我在实际写题时发现，很多人在递归函数里反复调不通，问题根源不是主体逻辑错了，而是边界条件没在写代码之前想清楚。

空树的情况最好处理：root为null时，没有任何路径，直接返回空数组。这里要小心的是，不能用“节点为 null 就形成一条路径”这种思路，因为路径一定要由真实节点组成，null 节点只是一个递归停止标志。

单节点树的情况也很典型：如果目标值等于根节点值，返回一个包含根值的路径，否则返回空。很多人会漏掉这种最小用例，导致递归函数在叶子节点判断时出错。叶子节点指的是左右孩子都是 null 的节点，判断条件必须是not node.left and not node.right，而不是node is None。

节点值可能为负数的情况更加隐蔽。当树里出现负数时，即使当前累计和已经超过目标值，继续走下去仍然可能因为加上负数而回到目标值。因此不能只凭数值大小做剪枝，这一点后面还会单独展开。

2. 核心推导：从遍历到回溯的层层递进

2.1 最朴素的前序遍历能拿到什么

递归解法的起点其实只是二叉树的前序遍历。前序遍历的顺序是根、左、右，它天然覆盖了所有根到叶子的路径，前提是在遍历过程中记录下当前路径。

先看一个很基础的前序遍历框架：

def dfs(node): if not node: return path.append(node.val) dfs(node.left) dfs(node.right) path.pop()

这段代码里，path是一个共享的列表，每次进入节点时把节点值加进去，处理完左右子树后把节点值弹出来。这个pop就是回溯的雏形：它保证在任何时候，path都恰好等于“从根到当前节点”的节点列表。

如果去掉path.pop()，遍历完左子树之后，左子树的所有节点还残留在path里，再进入右子树时，path变成了一条“从根到左子树再到右子树”的错误路径。想明白这一点，回溯的意义就已经掌握了一半。

2.2 加一个累计值，路径筛选就完成了

有了一条条完整的候选路径，接下来要做的事情就是筛选，筛选条件就是节点总和等于目标值。

这里有两种写法：一种是从 0 开始往上累加，每到一个节点把节点值加进去，到叶子时和 target 比较是否相等；另一种是从 target 开始往下减，每到一个节点把节点值减掉，到叶子时判断结果是否为 0。两种写法本质相同，后者代码上少维护一个变量，后面章节给出的标准实现用的就是递减写法。

在递归函数中，累计值很适合作为参数传入。每次调用dfs(node.left, cur_sum + node.left.val)，天然生成了当前递归分支独立的累计值，不会影响其他分支。这一点和path的共享方式形成鲜明对比，等下会详细解释。

2.3 回溯的精髓：加入路径和删除路径必须成对出现

上一节里，path.append(node.val)和path.pop()看起来像一对镜像操作，但为什么要做到成对出现，值得深入理解。

进入递归函数时，当前节点加入路径；在函数末尾、左右子树都处理完之后，当前节点从路径中弹出。这样每一个加入操作都对应一个删除操作，路径长度永远等于当前递归深度。这个“不能不删，不能多删，也不能删错顺序”的对称性，就是回溯的核心。

可以用一个简单的比喻来理解：递归向下深入就像往一根绳子上串珠子，每进入一个节点就串一颗，每从一个分支退回上一级就摘掉一颗。如果不摘珠子，下一次从另一个兄弟分支出发时，绳子上还挂着上一分支的珠子，得到的路径就绝不是“根到当前节点”的真实路径了。

在递归函数里，最容易犯的错误是只记得 append，不写 pop，或者把 pop 写进某个 if 分支里，导致部分路径删除失败。我的习惯是写完 append 之后立刻把 pop 写在函数末尾，两者之间就是左右子树的递归调用。

3. 完整可运行的递归解法与复杂度分析

3.1 标准写法：用目标值递减替代累加比较

下面是这道题最标准的 Python 解法，我把关键位置都加上了注释。

class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def path_sum(root, target): res = [] path = [] def dfs(node, remaining): if not node: return path.append(node.val) remaining -= node.val if not node.left and not node.right and remaining == 0: res.append(path[:]) dfs(node.left, remaining) dfs(node.right, remaining) path.pop() dfs(root, target) return res

这段代码里有几个地方值得逐一说清楚。

remaining的初值等于target，每经过一个节点就减去该节点的值。到叶子节点时，如果remaining == 0，就说明从根到这个叶子的累计和正好等于目标值。这种写法省去了维护cur_sum变量的麻烦。

res.append(path[:])是深拷贝，创建了一个全新的列表副本加入到结果集。如果直接写res.append(path)，后续path.pop()会修改同一个列表对象，最终结果集里的路径全都会被改坏，甚至全部变成空列表。这个坑我在后面“常见问题”里还会重点讲。

叶子判断必须用not node.left and not node.right。这样可以保证路径一定走到底，不会把半截路径算进去。

测试时可以用下面这段代码快速验证：

root = TreeNode(5) root.left = TreeNode(4) root.right = TreeNode(8) root.left.left = TreeNode(11) root.left.left.left = TreeNode(7) root.left.left.right = TreeNode(2) root.right.left = TreeNode(13) root.right.right = TreeNode(4) root.right.right.left = TreeNode(5) root.right.right.right = TreeNode(1) print(path_sum(root, 22)) # 输出: [[5, 4, 11, 2], [5, 8, 4, 5]]

我也建议你分别用target = 26和target = 18跑一下，前者对应[5, 8, 13]，后者对应[5, 8, 4, 1]，这样可以验证代码是否正确地处理了多路径筛选。

3.2 Java 与 JavaScript 实现中的三个细节

不同语言在递归回溯上的形式基本一致，但在“拷贝路径”和“节点为空”的判断上有几个细节点。

Java 版本可以这样写：

class Solution { List<List<Integer>> res = new ArrayList<>(); List<Integer> path = new ArrayList<>(); public List<List<Integer>> pathSum(TreeNode root, int target) { dfs(root, target); return res; } private void dfs(TreeNode node, int remaining) { if (node == null) { return; } path.add(node.val); remaining -= node.val; if (node.left == null && node.right == null && remaining == 0) { res.add(new ArrayList<>(path)); } dfs(node.left, remaining); dfs(node.right, remaining); path.remove(path.size() - 1); } }

Java 中最重要的就是new ArrayList<>(path)，它和 Python 的path[:]一样，是拷贝当前路径而不是把引用放进去。另外注意路径删除用的是path.remove(path.size() - 1)，因为 Java 的List.remove(int)方法接收的是下标，如果误用了remove(path.size())会越界。

JavaScript 版本的差异集中在浅拷贝与深拷贝上：

var pathSum = function (root, target) { const res = []; const path = []; const dfs = (node, remaining) => { if (!node) return; path.push(node.val); remaining -= node.val; if (!node.left && !node.right && remaining === 0) { res.push([...path]); } dfs(node.left, remaining); dfs(node.right, remaining); path.pop(); }; dfs(root, target); return res; };

[...path]是 ES6 的展开语法，效果等同于拷贝数组。这里很容易写成res.push(path)，后果和 Python 里的res.append(path)完全一样。

3.3 时间复杂度：为什么不能简单说 O(n)

很多人写复杂度时习惯直接写“每个节点访问一次，所以时间复杂度是 O(n)”，这个说法在面试里其实不够严谨。

递归遍历本身确实是每个节点最多访问一次，这部分是 O(n)。但题目要求输出所有符合条件的路径，每找到一条路径就要把整条路径拷贝一份，这个拷贝成本不能忽略。假设树是高度为 h 的满二叉树，叶子的数量是 O(n)，每条路径的长度是 O(h)，那么在极端情况下输出路径的总代价是 O(n * h)。对平衡树来说 h 是 O(log n)，所以这部分是 O(n log n)；对退化成链表的树来说，虽然路径只有一条，但路径长度是 O(n)，拷贝这条路径的代价也是 O(n)。

空间复杂度方面，递归调用栈的深度等于树高，是 O(h)，path列表在最深时也是 O(h)，结果集占用的空间要看符合条件的路径数量。综合来看，空间是 O(n * h) 这个量级。

在面试里，我会把“遍历部分是 O(n)，加上路径拷贝之后整体可以认为是 O(n log n) 到 O(n^2)，具体取决于树形”这个结论完整说出，面试官通常都会认可这个更细致的分析。

3.4 为什么用 member 变量要特别小心

很多题目模板会鼓励把res和path定义成类的成员变量，这样写起来方便，但要注意多次调用之间的状态污染。

如果在一个进程里多次调用同一个Solution实例的pathSum方法，成员变量res和path会延续上一次调用留下的数据，导致第二次调用一开始结果里就残留着旧数据。解决方法是把这两个变量定义在pathSum方法内部，让嵌套的dfs通过闭包访问它们，每次调用自动初始化，这也是我在 3.1 代码里采用嵌套函数写法的原因。

4. 高频踩坑与排查技巧实录

4.1 结果集里全是同一条路径，深拷贝救了命

这是这道题发生率最高的一类 bug。现象很好认：代码跑出来的结果，所有路径长得一模一样，或者全部是空列表。

原因在递归结束后，path最后一次被pop()清空，如果结果里保存的是path的引用，那么所有保存的引用都指向同一个不断变化的列表对象，最终看到的内容只会是最后的状态。

用照片来类比：直接append(path)相当于记录下了“放着照片的相框”的位置，但相框里的照片一直在换；append(path[:])才相当于把当前照片重新洗印了一张，保存下来。加不加这个切片，结果天差地别。

排查时可以打印res和path在递归过程中的变化，很容易定位到res.append(path)这一行。

4.2 只搜出一条路径，递归调用写错了位置

另一种常见 bug 是“明明有多条符合条件，结果只返回了一条”。问题往往出在提前return上。

看下面这个有 bug 的写法：

def dfs(node, remaining): if not node: return path.append(node.val) remaining -= node.val if not node.left and not node.right and remaining == 0: res.append(path[:]) return dfs(node.left, remaining) dfs(node.right, remaining) path.pop()

单独看，叶子节点没有左右子树，所以return似乎不影响后面的递归。但实际在递归过程中，一旦在当前叶子节点找到一条符合条件路径就直接返回，并跳过了path.pop()，路径中残留着当前叶子节点。这时它的兄弟分支如果还没遍历，路径状态就已经被破坏了。

还有一些人会写成：只要remaining == 0就记录并返回，没有判断节点是否为叶子。这样会产生“到一半就记一条路径”的错误结果，因为题目要求的是完整根到叶路径。正确逻辑是：叶子判断和剩余值判断必须同时成立，而且无论是否符合条件，都要继续递归左右子树，最后统一 pop。

4.3 负数节点会让剪枝直接失效

在没有负数的时候，可以加一个剪枝优化：如果remaining < 0，继续深入下去只会让和越来越大，不可能回到目标值，所以可以直接停止递归。

但是一旦树的节点值允许为负数，这个剪枝就是致命的。比如路径[5, -1, 1]求目标值 5，走到第二个节点时remaining是 1，走到第三个节点时又回到了 1？换个例子：目标值是 5，路径为[5, -10, 10]，在走到第二个节点时remaining = 0，如果按“remaining 减到 0 就停止剪枝”来写，这条路径就会被漏掉，其实继续走-10和10之后remaining会重新变回 5，路径总和依然是 5。负数导致的这种“先减后加”完全打破单调性。

所以，除非题目明确说明“节点值均为正数”，否则不要使用基于数值大小的剪枝。这个坑在题目平台的测试用例里几乎一定会出现，因为出题人深知这里容易犯错。

4.4 全局状态残留与递归深度超限

除了res和path，递归函数里尽量不要再去操作其他外部可变状态。某些实现会把当前累计和存在一个成员变量里，返回时做减法恢复，这种做法也能工作，但一旦某个分支提前return，恢复逻辑容易漏执行，bug 非常难查。推荐的仍是把累计值作为参数传递，它天然不可变、不需要手动恢复。

递归深度超限也有可能出现。当二叉树退化成一条链，高度达到几千甚至上万时，Python 默认递归深度限制是 1000 左右，程序会直接抛出递归错误。此时可以提高递归限制，比如sys.setrecursionlimit(10000)，但这属于治标不治本。更稳妥的方案是改成显式栈迭代，虽然代码会比递归版本复杂不少，但能彻底摆脱递归深度限制。在算法面试的常规数据范围内，递归版本不会有问题。

5. 一个题目标题背后的变体地图

5.1 变体一：只问是否存在路径而不是输出路径

很多面试题会把“输出所有路径”改成“判断是否存在一条路径”，这时解法可以变得非常简洁，甚至不需要维护 path 和回溯：

def has_path(node, target): if not node: return False if not node.left and not node.right: return target == node.val return has_path(node.left, target - node.val) or has_path(node.right, target - node.val)

这个版本只需要返回布尔值，因此递归函数天然具备“短路”效果，一条路径成功就返回 True。它和输出路径版本的差别，就在于省去了路径收集和回溯恢复。

如果你能熟练解释清楚两个版本之间为什么一个需要回溯、一个不需要，说明你是真的理解了递归状态，而不是背熟了某段代码。

5.2 变体二：路径起点不再固定为根

标题里带着“（一）”，说明后面大概率会扩展出更难版本。一个很常见的升级是“路径可以从任意节点出发，到任意节点结束”，不再要求从根开始。

这个变体中，最简单的思路是把每个节点都当作一次起点，对它递归搜索“以它为根、向下延伸的所有路径”。这样外层需要一次遍历，内层再跑一次路径搜索，复杂度会上升到 O(n²)。虽说这种写法不是最优，但它和本题目“递归 + 回溯”的思路一脉相承，面试时先给出暴力版再去优化，也是很正常的节奏。

5.3 变体三：前缀和把任意路径问题优化到 O(n)

如果任意起止路径的变体数据量很大，O(n²) 就不够看了，这时候需要引入前缀和技巧。

树的前缀和定义是“从根节点到当前节点的路径上所有节点值之和”。任意一条从上到下的路径和，都可以表示为两个前缀和的差值。比如当前节点的前缀和是curSum，某个祖先节点的前缀和是preSum，那么从祖先节点的子节点到当前节点这条子路径和就是curSum - preSum。

只要在递归遍历时用一个哈希表记录“某个前缀和出现过多少次”，就可以在遍历到每个节点时 O(1) 判断是否存在以该节点为终点的、和为 target 的路径。同样要注意：递归返回时要对称地删除当前前缀和的记录，这和 path 的回溯逻辑如出一辙。这个技巧我不会在这篇文章里展开全部细节，但它非常值得作为后续系列的下一期内容。

回到文章开头那棵树，当你能够闭着眼睛写出标准递归解，同时知道深拷贝、叶子判断、负数陷阱这三个关键点，这道题就算真正吃透了。我的体会是：这类题目千万不要死记代码，拿一张纸画一棵五六层的小树，用递归调用栈的顺序手动走一遍，看看 path 在每个节点进入和退出时分别是多少，把这一遍想明白了，再复杂的路径变体你也很难被绕进去。标题写“（一）”，说明路径系列后面还有文章可做，不过在那之前，先把根到叶这个版本磨到滚瓜烂熟，收益比一口气追完所有变体大得多。