[113] 路径总和 II

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有从根节点到叶子节点路径总和等于给定目标和的路径。
叶子节点是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]
示例 2：
输入：root = [1,2,3], targetSum = 5
输出：[]
示例 3：
输入：root = [1,2], targetSum = 0
输出：[]

这道题是路径总和系列的第二题，相比 [112] 路径总和只需要判断是否存在，本题要求收集所有满足条件的完整路径，因此需要在 DFS 遍历时维护当前路径，并在到达叶子节点且路径和满足条件时记录结果。

核心思路是回溯：在前序位置将当前节点加入路径、扣减目标值，然后递归左右子树，最后在后序位置将节点从路径中移除，恢复状态。

需要注意的是，path 是引用类型（数组），所有递归层共享同一个数组，因此必须在后序位置手动 pop 来回溯。而 rest 是值类型（number），每层递归有自己的副本，无需手动恢复。

function pathSum(root: TreeNode | null, targetSum: number): number[][] {
  const res: number[][] = [];
  if (!root) return res;

  function helper(node: TreeNode, path: number[], rest: number) {
    // 前序位置：做选择
    path.push(node.val);
    rest -= node.val;

    // 到达叶子节点且路径和满足条件，收集结果
    if (!node.left && !node.right && rest === 0) {
      res.push([...path]);
    }

    node.left && helper(node.left, path, rest);
    node.right && helper(node.right, path, rest);

    // 后序位置：撤销选择（回溯）
    path.pop();
  }

  helper(root, [], targetSum);
  return res;
}

本题也可以使用迭代方式实现。迭代时所有状态（path、rest）都只有一份，全局共享，因此 path 和 rest 都需要手动恢复。

另外，由于 path.push 发生在前序位置，path.pop 发生在后序位置——节点必须在左右子树都遍历完之后才能从路径中移除——因此迭代版本需要使用后序遍历的模板，通过 prev 指针判断右子树是否已经访问过，从而确定何时可以安全回溯。

function pathSum(root: TreeNode | null, targetSum: number): number[][] {
  const res: number[][] = [];
  if (!root) return res;

  const stack: TreeNode[] = [];
  let node: TreeNode | null = root;
  const path: number[] = [];
  let rest: number = targetSum;
  let prev: TreeNode | null = null;

  while (node || stack.length) {
    while (node) {
      // 前序位置：做选择
      path.push(node.val);
      rest -= node.val;

      if (!node.left && !node.right && rest === 0) {
        res.push([...path]);
      }

      stack.push(node);
      node = node.left;
    }

    const curr = stack[stack.length - 1];

    if (curr.right && prev !== curr.right) {
      // 右子树还没访问过，先去右子树
      node = curr.right;
    } else {
      // 后序位置：左右子树都遍历完了，安全回溯
      stack.pop();
      path.pop();
      rest += curr.val;
      prev = curr;
    }
  }

  return res;
}

[113] 路径总和 II ​

[113] 路径总和 II