路径总和 II 如何用回溯记录根到叶子的所有路径？

简化版

路径总和 II 要找所有从根到叶子、节点值之和等于目标的路径。

DFS 时维护当前路径 path 和剩余目标 remain。

走到叶子节点时，如果 remain === node.val，就把当前路径复制进答案；返回上一层前要撤销当前节点。

详细版

这题是树上的回溯。

每到一个节点，把节点值加入路径，并把剩余目标减去节点值。只有当节点是叶子节点时，才判断是否构成完整路径。

如果不是叶子，就继续递归左右子树。

注意加入答案时要复制路径，比如 [...path]，否则后续回溯修改路径会影响已保存结果。

时间复杂度最坏 O(n * h) 或按输出规模计算，空间复杂度是递归栈和路径的 O(h)。

完整版教学

一、为什么这是树上的回溯

根到叶子的路径是一个逐层选择过程：从根开始，每一层选择走左孩子或右孩子，直到叶子。DFS 天然适合枚举树路径，而回溯负责维护“当前走过的路径”。当递归返回父节点时，要撤销子路径的选择，继续尝试另一个分支。

记忆钩子：树路径题的回溯动作就是“进节点 push，出节点 pop”。

二、为什么必须到叶子才判断

题目要求的是根到叶子路径，不是任意向下路径。即使中间某个节点累计和已经等于目标，只要它不是叶子，也不能加入答案。叶子的定义是左右孩子都为空。

节点类型	和等于目标	是否加入答案
中间节点	是	不加入
叶子节点	是	加入
叶子节点	否	不加入

这个边界非常容易漏。

三、剩余目标比累计和更好讲

可以维护当前累计和，也可以维护剩余目标。剩余目标的写法是每进入一个节点，就让 remain -= node.val。到叶子时，如果剩余目标正好等于当前节点值，或者扣完后为 0，就找到一条合法路径。

目标 22
路径 5 -> 4 -> 11 -> 2
剩余变化：22 -> 17 -> 13 -> 2 -> 0

这种写法能直观看到目标被路径逐步消耗。

四、代码模板

实现如下：

function pathSum(root, targetSum) {
  const ans = []
  const path = []

  function dfs(node, remain) {
    if (!node) return
    path.push(node.val)
    const next = remain - node.val
    if (!node.left && !node.right && next === 0) {
      ans.push([...path])
    } else {
      dfs(node.left, next)
      dfs(node.right, next)
    }
    path.pop()
  }

  dfs(root, targetSum)
  return ans
}

path.pop() 必须执行，无论当前节点是否命中答案，都要恢复父层状态。

五、复制路径为什么必要

path 是回溯过程中复用的数组。如果把 path 本身放入答案，后续 pop 和 push 会改变答案里的引用。加入答案时使用 [...path]，保存的是当前路径快照。

ans.push([...path])

这个细节在所有“收集路径列表”的回溯题里都很重要。

六、常见误区与追问

误区：中间节点和达标就加入答案。 题目要求根到叶子路径，必须走到叶子。
误区：加入答案时不复制 path。 后续回溯会把答案改坏。
误区：忘记 pop。 当前路径会污染兄弟分支。
追问：节点值有负数还能剪枝吗？ 有负数时不能用 remain 小于 0 直接剪枝。
追问：复杂度为什么和输出有关？ 每条答案路径都要复制，复制成本与路径长度有关。

这些问题考的是树路径定义和回溯状态管理。

七、加强记忆

路径总和 II 记成“根到叶，push/pop，命中复制”。DFS 进入节点时加入路径并扣减目标；只有叶子节点剩余为 0 才收集答案；收集时复制路径，返回时撤销节点。遇到负数时别乱剪枝，因为后面可能被负数或正数重新调整。

简化版

详细版