路径总和 I、II、III 怎样做？III 为什么要用前缀和？

简答

路径总和 I（LeetCode 112）问二叉树里有没有一条从根到叶子的路径，节点值加起来等于 targetSum。做法是 DFS：每往下走一个节点，就把目标值减去这个节点的值，走到叶子时看剩下的是不是 0。叶子指左右孩子都为空的节点，空树直接返回 false。

路径总和 II（LeetCode 113）要把所有满足条件的根到叶子路径都列出来。DFS 时用一个数组记录当前走过的节点，到叶子且和对上了，就把数组复制一份放进结果；从一个节点返回时把它从数组里弹出，这就是回溯。

路径总和 III（LeetCode 437）放宽了起点和终点，路径可以从任意节点开始、在任意节点结束，但必须一路向下。对每个节点都往下暴力枚举是 O(n²)。更好的办法是把根到当前节点这条链看成一个数组，套用“和为 K 的子数组”的前缀和思路：用 Map 记录这条链上每个前缀和出现了几次，当前前缀和减去 targetSum 出现过几次，就有几条以当前节点结尾的路径，整体 O(n)。

III 最容易错的是回溯：离开一个节点时，要把它的前缀和计数减 1，因为它不在兄弟子树的那条链上。另外 Map 里要先放 0 → 1，表示从根开始的路径。

I 和 II：从根到叶子

下面先用 LeetCode 的层序数组建树，null 表示空位。示例树来自 LeetCode 113 的示例 1。

JavaScript

function fromLevelOrder(values) {
  if (values.length === 0 || values[0] === null) return null;
  const root = { val: values[0], left: null, right: null };
  const queue = [root];
  let i = 1;
  for (let head = 0; i < values.length; head++) {
    const node = queue[head];
    for (const side of ['left', 'right']) {
      if (i < values.length && values[i] !== null) {
        node[side] = { val: values[i], left: null, right: null };
        queue.push(node[side]);
      }
      i++;
    }
  }
  return root;
}

function hasPathSum(root, target) {
  if (!root) return false;
  if (!root.left && !root.right) return target === root.val;
  const rest = target - root.val;
  return hasPathSum(root.left, rest) || hasPathSum(root.right, rest);
}

function pathSum(root, target) {
  const result = [];
  const path = [];
  function dfs(node, rest) {
    if (!node) return;
    path.push(node.val);
    rest -= node.val;
    if (!node.left && !node.right && rest === 0) result.push([...path]);
    dfs(node.left, rest);
    dfs(node.right, rest);
    // 回到父节点前，把自己从路径里拿掉
    path.pop();
  }
  dfs(root, target);
  return result;
}

const tree = fromLevelOrder([5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1]);
console.log(String(hasPathSum(tree, 22))); // true
console.log(String(hasPathSum(fromLevelOrder([1, 2, 3]), 5))); // false
console.log(JSON.stringify(pathSum(tree, 22))); // [[5,4,11,2],[5,8,4,5]]
console.log(String(hasPathSum(null, 0))); // false

为什么判断要放在叶子上，而不是“剩余为 0 就返回”？因为题目要的是根到叶子的路径。如果走到一个中间节点时剩余刚好为 0，下面还有孩子，这条路径并没有走完，不算数。

II 里为什么要 [...path] 复制一份？因为 path 是整个 DFS 共用的数组，后面还会被 push 和 pop。直接把它放进结果，最后结果里所有路径都会指向同一个已经被弹空的数组。

III：路径可以从中间开始

先看为什么前缀和能用上。从根到当前节点是一条链，设这条链上的前缀和是 sum。如果链上某个祖先位置的前缀和是 sum - targetSum，那么从它下一个节点到当前节点这一段的和正好是 targetSum。所以只要知道链上有几个前缀和等于 sum - targetSum，就知道有几条以当前节点结尾的路径。这和数组里的做法一样，见《前缀和与差分怎样用？和为 K 的子数组为什么要配哈希表？》。

JavaScript

function fromLevelOrder(values) {
  if (values.length === 0 || values[0] === null) return null;
  const root = { val: values[0], left: null, right: null };
  const queue = [root];
  let i = 1;
  for (let head = 0; i < values.length; head++) {
    const node = queue[head];
    for (const side of ['left', 'right']) {
      if (i < values.length && values[i] !== null) {
        node[side] = { val: values[i], left: null, right: null };
        queue.push(node[side]);
      }
      i++;
    }
  }
  return root;
}

function pathSumIII(root, target) {
  // 0 出现 1 次，表示从根节点开始的路径
  const counts = new Map([[0, 1]]);
  function dfs(node, sum) {
    if (!node) return 0;
    sum += node.val;
    let found = counts.get(sum - target) ?? 0;
    counts.set(sum, (counts.get(sum) ?? 0) + 1);
    found += dfs(node.left, sum) + dfs(node.right, sum);
    // 离开这个节点，它的前缀和不属于兄弟子树那条链
    counts.set(sum, counts.get(sum) - 1);
    return found;
  }
  return dfs(root, 0);
}

console.log(pathSumIII(fromLevelOrder([10, 5, -3, 3, 2, null, 11, 3, -2, null, 1]), 8)); // 3
console.log(pathSumIII(fromLevelOrder([5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1]), 22)); // 3
console.log(pathSumIII(fromLevelOrder([1, -1]), 0)); // 1

第一组是 LeetCode 437 的示例 1，和为 8 的路径有 5 → 3、5 → 2 → 1、-3 → 11 三条。

为什么要先查 sum - target 再把 sum 加进 Map？因为路径至少包含一个节点。先加再查，当 target 为 0 时，当前节点会和自己配对，多数出一条长度为 0 的“路径”。最后一组 [1,-1] 中，和为 0 的路径只有 1 → -1 一条，结果是 1；顺序写反的话，每个节点都会和自己配对，结果变成 3。

为什么离开节点时要减回去？Map 里应该只有根到当前节点这条链上的前缀和。左子树遍历完转到右子树时，左子树里的节点已经不在链上了，如果不减掉，右子树的节点会和左子树的节点配对，可它们之间根本没有向下的路径。

时间上每个节点只访问一次，Map 操作平均常数时间，整体 O(n)；空间是 O(h)，h 是树高，来自递归深度和 Map 里的链。LeetCode 437 的节点值范围是 -10⁹ 到 10⁹，最多 1000 个节点，前缀和最大约 10¹²，在 JavaScript 的安全整数范围内。

常见追问

III 的暴力解法是什么？

对每个节点，把它当起点往下 DFS，统计和等于目标值的路径数；再对所有节点重复。每个节点作为起点要往下走一遍，平衡树时约 O(n log n)，退化成链时是 O(n²)。

II 为什么不在 dfs 里传 [...path, node.val] 的新数组？

也能写对，而且不用手动 pop。但每层都复制一次数组，额外开销和路径长度成正比。共用一个数组加回溯，只在找到答案时复制。