CS-Notes 剑指 Offer 34：二叉树中和为某一值的路径 —— 回溯法求根到叶路径全解

本篇基于 CS-Notes 仓库中 34. 二叉树中和为某一值的路径 的题解展开，围绕"输入一棵二叉树和一个整数，找出所有从根结点到叶结点、结点值之和恰好等于目标值的路径"这一经典面试题，完整讲解题目约束、Java 回溯解法、易错边界（非叶结点提前和为目标值、负数值、路径拷贝）以及时间空间复杂度分析。读完本篇，你应能独立完成"根到叶路径和"类问题的回溯模板编写，并理解该模板与矩阵路径、搜索树遍历等其它题型的共通之处。

题目描述与关键约束

原题如下（引自 notes/34. 二叉树中和为某一值的路径.md）：

输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

以图示示例为例：目标值为 22 时，存在两条路径——10 → 5 → 7 与 10 → 12。从图中可以看出两条路径的关键区别：12 是右子结点且没有子结点，本身就是叶结点，因此 10 + 12 = 22 直接成路径；而左子树中 10 + 5 = 15 未达到 22，必须继续向下走到叶结点 4（和为 19，不是路径）或 7（和为 22，是路径）。

这里有两条约束决定了算法形态：

1. 路径起点必须是根结点：不允许从任意子结点出发，因此只需从 root 出发做一遍深度优先搜索，不存在多起点重复搜索的问题。
2. 路径终点必须是叶结点（左右子结点均为空）：这是本题最易踩坑的约束——若某条非叶路径的累加和恰好等于 target，也不能记录，必须继续向下走。

回溯解法：完整实现与逐行剖析

原仓库给出的标准解法如下（完整保留，未做删节）：

private ArrayList<ArrayList<Integer>> ret = new ArrayList<>();

public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
    backtracking(root, target, new ArrayList<>());
    return ret;
}

private void backtracking(TreeNode node, int target, ArrayList<Integer> path) {
    if (node == null)
        return;
    path.add(node.val);
    target -= node.val;
    if (target == 0 && node.left == null && node.right == null) {
        ret.add(new ArrayList<>(path));
    } else {
        backtracking(node.left, target, path);
        backtracking(node.right, target, path);
    }
    path.remove(path.size() - 1);
}

这段实现是标准的"选择—递归—撤销选择"三段式回溯，逐段剖析如下：

• 选择（进入节点）：path.add(node.val) 把当前结点值压入路径；同时 target -= node.val 采用"剩余目标和"代替"当前累加和"，用减法维护目标差值，避免额外维护 sum 参数。
• 终止判定：target == 0 && node.left == null && node.right == null 两个条件缺一不可。前一个条件保证"和恰好达标"，后一个条件保证"终点是叶结点"。如果只判断和为 0，就会把 10 → 5（若和为 15 的目标值场景）这类中间路径错误地记录下来。
• 递归展开：未满足终止条件时，继续向左、右子树搜索。注意此时 target 可能已经为 0 而结点不是叶结点（例如中间路径和恰好为 0，后续还有负数值），代码仍会继续向下递归——这正是负数值场景下仍能正确搜索的原因。
• 撤销选择（回溯）：path.remove(path.size() - 1) 在子树搜索结束后弹出当前结点，使 path 恢复到进入本结点之前的状态。这一步保证了同一条 path 实例可以在不同分支间安全复用，全程只有一个 List 对象被反复增删，而不必为每个分支新建列表。
• 结果拷贝：ret.add(new ArrayList<>(path)) 在命中时创建的是 path 的浅拷贝。由于 path 随后还要继续被增删，若直接把引用 path 加进 ret，所有记录到的路径最终都会指向同一个被改写的列表，输出时全部错乱。这是本题在面试手写代码中最常见的 Bug 点。
• 空树处理：node == null 直接返回，天然覆盖了 root == null 的输入（返回空列表）以及递归到叶子边界的情形。

复杂度分析

从源码结构看，回溯过程等价于对整棵二叉树做一次深度优先遍历：

• 时间复杂度：最坏情况下需要访问全部 n 个结点，每个结点上的 add/remove 操作为 O(1)；每次命中一条路径时需要拷贝长度为 h（树高）的列表。因此整体为 O(n·h)。对于退化成链表的树，h = n，退化为 O(n²)；对于满二叉树，h = log n，约为 O(n log n)。若不计拷贝、只看结点访问，则与一次 DFS 相同，为 O(n)。
• 空间复杂度：递归栈深度为树高 h，path 列表最大长度也是 h，故额外空间为 O(h)（不计输出 ret 本身占用的空间）。

易错点与边界场景清单

结合上述实现，整理一份自查清单，面试或自测时可逐项核对：

场景	正确行为	常见错误
root == null	返回空列表，不抛异常	未判空直接解引用
非叶结点路径和恰好等于 target	不记录，继续向下搜索	只判 target == 0 就记录
存在负数值，中途和为 0 但后续可回到 0	继续递归，后续仍可能命中	一旦 target == 0 就剪枝停止
多条路径同时满足	全部记录，顺序为 DFS 序（先左后右）	找到第一条就返回
命中路径的保存	new ArrayList<>(path) 拷贝	直接存 path 引用，结果被后续增删污染

其中"负数值不能剪枝"一点值得强调：如果题目约定结点值均为正数，则 target < 0 时可以安全剪枝；但原题并未做此约定，所以上面实现中一旦 target 变负只是继续搜索而非剪枝，这是鲁棒写法的体现。

同一模板在仓库其它题解中的复用

"DFS + 局部状态 + 回溯清除状态"这一套模板在 CS-Notes 的其它剑指 Offer 题解中反复出现，可以对照阅读加深理解：

• 12. 矩阵中的路径：同样使用回溯法搜索所有可能走向，区别在于用"已访问标记"代替路径列表，搜索结束时将标记清除；
• 13. 机器人的运动范围：文中明确指出"回溯是深度优先搜索的一种特例，它在一次搜索过程中需要设置一些本次搜索过程的局部状态，并在本次搜索结束之后清除状态"，与本题 path.add / path.remove 的成对操作是同一思想；
• 二叉树其它章节（如 26. 树的子结构、32.1 从上往下打印二叉树 等，见 剑指 Offer 题解目录）则展示了二叉树上各类遍历与状态维护的写法，可作为本题的上下文知识储备。

本题与 Leetcode 上"Path Sum II"是同一问题模型：递归版即上述回溯模板；若改为迭代实现，可以用显式栈保存 (结点, 目标差值, 路径快照) 三元组，代价是每次入栈需要拷贝路径前缀，可读性和空间开销都不如递归版，面试中优先推荐递归写法。

小结

• 题目要求"根到叶、和为 target 的所有路径"，两条约束（起点必为根、终点必为叶）直接决定了"单次 DFS + 叶结点终止判定"的算法形态；
• 回溯模板的核心是三步：进入时更新状态（path.add、target 递减）、命中叶结点时拷贝记录、离开时撤销状态（path.remove）；
• 记录路径必须拷贝列表；存在负数值时不能以"和已为 0 或已超目标"为由剪枝；
• 该模板与 矩阵中的路径、机器人的运动范围 等题解共用同一套 DFS 回溯思想，掌握后可迁移到大量"搜索所有合法路径/方案"类题目。