LeetCode 113. 路径总和 II
题目描述
题意分析
找出所有从根节点出发、沿父子连接一直走到叶子节点的路径，要求每条路径的节点值之和等于
targetSum，返回各条路径从根到叶子的完整节点值序列。叶子必须左右孩子都为空，途中某个前缀的和等于目标不能作为答案。本题要求收集全部匹配路径，找到一条后还要继续搜索其他分支。不同分支即使得到相同的值序列，也分别对应一条路径，不应按数值去重。空树或没有匹配路径时返回空列表；节点值和目标都可能为负数。
解法：DFS 回溯记录根到叶路径
核心思路
[!blue]
从根向下搜索时，当前路径只会在末尾增加或移除节点，因此适合用 DFS 配合回溯。调用
dfs(node, remain)之前，path保存从根到当前节点父亲的值，remain等于原目标减去这些祖先值之和，仍然包含当前节点需要贡献的部分。进入非空节点后，把它的值加入
path。若它是叶子，当前路径已经完整；此时remain == node.val恰好表示整条路径和等于目标，可以保存答案。若还要搜索孩子，就把remain - node.val传下去，使子调用继续满足同一个状态定义。左右分支共用同一份
path。一个子调用结束时，必须删掉它自己加入的节点，使路径恢复成进入该调用之前的状态。这样搜索完左子树后，路径重新停在当前节点，右子树不会带上左边分支的内容。即使当前节点刚好命中答案，返回之前也必须执行这一步撤销。答案不能直接保存共享路径本身。Java 的列表对象会继续被修改，Go 的切片也可能共用底层数组；必须复制当前路径，才能让已经找到的答案独立于后续回溯。
remain则按值传给子调用，各层拥有自己的值，无需像path一样手动恢复。每个节点沿唯一的根路径被访问一次，每片叶子对应一条完整候选路径，因此遍历所有分支就能找全答案。由于后面的节点可能是负数，即使当前累计和超过目标，也不能据此剪枝。
解题步骤
- 创建结果列表和共享路径，以根节点及原目标调用 DFS。
- 当前节点为空时直接返回；否则将当前值加入路径。
- 若左右孩子都为空且
remain == node.val，复制当前路径加入结果。- 未命中上述条件时，分别对左右孩子递归，传入
remain - node.val；空孩子会立即返回。- 在本层返回前删除路径末尾的当前节点，恢复父调用的路径状态。
- 所有分支搜索完后，返回收集到的全部路径。
代码实现
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
dfs(root, targetSum, path, res);
return res;
}
private void dfs(TreeNode node, int remain, List<Integer> path, List<List<Integer>> res) {
if (node == null) {
return;
}
path.add(node.val);
if (node.left == null && node.right == null && remain == node.val) {
// 当前路径会继续回溯修改，加入答案时必须复制。
res.add(new ArrayList<>(path));
} else {
dfs(node.left, remain - node.val, path, res);
dfs(node.right, remain - node.val, path, res);
}
// 命中答案后也要撤销当前节点，避免污染后续分支。
path.remove(path.size() - 1);
}
}
func pathSum(root *TreeNode, targetSum int) [][]int {
res := make([][]int, 0)
path := make([]int, 0)
var dfs func(*TreeNode, int)
dfs = func(node *TreeNode, remain int) {
if node == nil {
return
}
path = append(path, node.Val)
if node.Left == nil && node.Right == nil && remain == node.Val {
// 复制当前路径，避免后续回溯覆盖结果。
onePath := append([]int(nil), path...)
res = append(res, onePath)
} else {
dfs(node.Left, remain-node.Val)
dfs(node.Right, remain-node.Val)
}
// 命中答案后也要撤销当前节点，避免污染后续分支。
path = path[:len(path)-1]
}
dfs(root, targetSum)
return res
}
复杂度分析
- 时间复杂度：$O(n + S)$，
n为节点数，S为所有答案路径的长度总和。遍历与回溯处理每个节点一次，另需花费S的时间复制结果；最坏为 $O(nh)$，h为树高。- 空间复杂度：$O(h)$，递归栈和当前路径都至多包含一条根到叶路径；不计返回结果所占的 $O(S)$ 空间。
关键点总结
[!green]
remain扣除了祖先，尚未扣除当前节点，与叶子处的比较方式配套。- 加入当前节点和离开时撤销成对出现，让每个子调用恢复进入前的共享路径。
- 保存路径副本，才能避免后续回溯修改已有答案。
- 找到一条只表示收集到一个结果，仍要搜索其他分支。
易错点总结
[!yellow]
- 直接保存共享
path，后续删除或覆盖会改变之前的答案；Java 列表和 Go 切片都需要复制。- 只判断路径和，不判断叶子，会收集尚未完整走到底的路径。
- 用左右孩子为空的“或”条件判断叶子，会把只有一个孩子的节点误判为终点。
- 命中后提前返回而没有撤销当前节点，会污染后续兄弟分支的路径。
- 按剩余目标为负进行剪枝，会漏掉后面包含负数的合法路径。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 112. 路径总和 | 简单 | 匹配条件相同，原题只返回布尔值，本题需要维护路径并在命中时复制。 |
| 437. 路径总和 III | 中等 | 原题统计任意起点的向下路径，本题只收集根到叶的完整路径。 |
| 257. 二叉树的所有路径 | 简单 | 回溯维护从根到当前节点的路径；本题复制并输出全部目标和叶路径，该题输出所有根到叶的字符串路径。 |
| 129. 求根节点到叶节点数字之和 | 中等 | 回溯维护从根到当前节点的路径；本题复制并输出全部目标和叶路径，该题逐层按十进制累加根到叶数字。 |
| 666. 路径总和 IV | 中等 | 路径总和系列。II 记录满足目标和的具体路径；IV 对编码树累加所有根到叶路径和。 |