LC113 路径总和 II · 逐题动画 · RuntimeScope

RuntimeScope/算法实验台/56 天打卡/141 题/LC113

题型地图 56天全屏 141题

当前：LC113 · 路径总和 II · 首次出现于 Day 22 · 路径：顶栏「56天打卡」→ 点击 LC 题号 → 逐题动画

← LC112 LC114 →

50 / 141回到 Day 22 卡片 141 题索引

LC113 · 路径总和 II · 工程执行实验室

路径收集台 · DFS + 回溯

LC112 问有没有一条路；LC113 问把所有正确路线都交出来。核心是一路维护 path，到叶子判断，命中就复制一份，再回溯撤销。

targetSum = 22

→ [[5,4,11,2], [5,8,4,5]]

LC112 vs LC113

LC112 · 路径总和 I

判断是否存在一条 root-to-leaf 路径和为 target，找到即可返回 true。

LC113 · 路径总和 II

返回所有满足条件的 root-to-leaf 路径，必须遍历完整棵树，不能提前结束。

LC112 问有没有一条路；LC113 问把所有正确路线都交出来。所以这题的核心不是返回 true，而是一路维护 path，到叶子判断，命中就复制一份，再回溯撤销。

DFS + 回溯流程

1. 进入：path.push(val)，remain -= val
2. 叶判断：是叶子且 remain === 0 → ans.push([...path])
3. 递归左右子树（不提前 return）
4. 退出：path.pop() 恢复现场

关联题目

LC112路径总和 I
判断是否存在，可提前返回 true。
LC437路径总和 III
任意向下路径，不要求到叶子。
LC257二叉树的所有路径
同样 DFS + 回溯收集所有 root-to-leaf 路径。

· LC112：存在一条 root-to-leaf 路径和为 target 即可返回 true，找到可提前结束。
· LC113：返回所有满足条件的 root-to-leaf 路径，必须遍历完整棵树，不能提前 return。

1/14 · LC112 对比

14 步分镜：

Step 1LC112 对比

LC112 vs LC113：有没有 vs 全部交出来

LC112 判断是否存在一条 root-to-leaf 路径和为 target，找到即可返回 true。LC113 要返回所有满足 targetSum 的 root-to-leaf 路径列表——不能提前结束，必须遍历完整棵树。

LC112 vs LC113

LC112：存在一条 root-to-leaf 路径和为 target 即可返回 true，找到可提前结束。
LC113：返回所有满足条件的 root-to-leaf 路径，必须遍历完整棵树，不能提前 return。
进入节点：path.push(val)，remain -= val。
叶子且 remain === 0：ans.push([...path])，必须复制 path。
退出节点：path.pop()，恢复现场，兄弟分支才能从正确前缀出发。

为什么

主状态 · node / remain / path / ans

当前节点 node

node = —

剩余目标 remain

当前路径 path

[]

答案列表 ans

[]

本步动作：—对比 LC112 / LC113

琥珀 = 当前 path·青 = 当前节点·绿 = 已收集路径上的节点

递归栈 · dfs(node, remain)

（空栈）

TypeScript · pathSum / dfs

1function pathSum(root, targetSum) {
2  const ans = []
3  const path = []
5  function dfs(node, remain) {
6    if (!node) return
8    path.push(node.val)
9    remain -= node.val
11    if (!node.left && !node.right && remain === 0) {
12      ans.push([...path])
13    }
15    dfs(node.left, remain)
16    dfs(node.right, remain)
18    path.pop()
19  }
21  dfs(root, targetSum)
22  return ans
23}

为什么要复制 path？

ans.push(path)

ans.push(path) — 保存的是同一个数组引用。后续回溯 path.pop() 时，ans 里的内容也会被改掉，最后可能变成空数组或错误路径。

ans.push([...path])

ans.push([...path]) — 给当前路径拍一张快照，后续 path 怎么变化，答案里的路径都不会变。

复杂度（非 O(n) / O(1)）

时间: O(N + K·H)，最坏 O(N²)
辅助空间: O(H) 辅助空间
含输出: 输出计入时：O(K·H)，最坏 O(N²)

N 为节点数：DFS 每个节点访问一次。K 为满足条件的路径条数，每收集一条需复制当前 path，成本 O(H)，H 为树高。

递归栈深度与当前 path 长度均为 O(H)。若把输出结果计入空间，则为 O(K·H)，最坏 O(N²)。

面试怎么说

这题用 DFS + 回溯。递归过程中维护一条从根到当前节点的 path，同时维护剩余目标 remain。进入节点时把值加入 path，并扣减 remain；如果当前节点是叶子且 remain 为 0，就把 path 的副本加入答案。递归左右子树后，需要 pop 当前节点，恢复现场，保证兄弟分支不会受到影响。时间复杂度是 O(N + K·H)，最坏 O(N²)，辅助空间 O(H)。

常见错误

只判断 remain == 0，没有判断必须是叶子

内部节点 remain 也可能为 0，但路径必须到叶子才算。必须同时检查 !left && !right。

找到一条路径后提前 return

LC112 可以短路；LC113 要收集全部路径，必须遍历完整棵树。

ans.push(path) 没有复制 path

ans.push(path) — 保存的是同一个数组引用。后续回溯 path.pop() 时，ans 里的内容也会被改掉，最后可能变成空数组或错误路径。

递归结束忘记 path.pop()

回溯不 pop，path 会带着上一分支的节点进入兄弟子树，答案全错。

把 root-to-leaf 误解成任意向下路径

任意向下路径是 LC437 的范围；本题必须走到叶子。