手帐 Blog

主题

复盘 · LC 437 路径总和 III ​

题目 ​

题意 ​

统计二叉树中路径和等于 targetSum 的条数。

  • 路径方向只能向下（父 → 子），不必从根开始，也不必到叶子。
  • 节点值可正可负。
  • 一条路径 = 一条向下的节点链。

边界：空树；单节点等于 / 不等于 target；负数导致「多段前缀」都可能命中。

涉及算法 ​

标签一句话
DFS + 路径枚举根到当前节点的路径上，枚举所有「以当前为终点」的后缀和
前缀和 + 哈希与 560 相同：count(prefix - target)；DFS 回溯时增减频次

教程对照：17 · 二叉树递归经典（112 路径总和）、08 · 前缀和（560 套路上树）。

评价我的解法 ​

思路本质对：沿路径维护节点值数组，在每个节点上检查所有以当前节点结尾的子路径和。但复杂度炸掉，118/130 TLE。

我的代码（摘自 437-路径总和三/index.js，不含本地测例）：

javascript
var pathSum = function (root, targetSum) {
  const pathArr = [];
  let resCount = 0;
  if (!root) {
    return 0;
  }
  function path(root, arr) {
    if (!root) {
      return;
    }
    const val = root.val;
    const newArr = [...arr, val];
    for (let i = 0; i <= arr.length; i++) {
      const sum = sumArr(newArr, i, arr.length);
      console.log(sum);
      if (sum === targetSum) {
        resCount++;
      }
    }
    path(root.left, newArr);
    path(root.right, newArr);
  }
  function sumArr(arr, i, j) {
    let sum = 0;
    for (let k = i; k <= j; k++) {
      sum += arr[k];
    }
    return sum;
  }
  path(root, []);
  return resCount;
};

评价：

  1. 语义对：for i 枚举起点、sumArr(i..当前) 正是「向下路径、任意起点」。小样例能过。
  2. 复杂度过高：每个节点对路径上每个起点再扫一遍求和 → 单点 O(depth²)，整树最坏接近 O(n³)；再加每次 [...arr, val] 拷贝，雪上加霜。
  3. console.log 留在热路径：提交里日志也会拖慢，必须删。
  4. 没用上前缀和：从 i 到末尾的区间和，用「当前前缀 − 起点前缀」一次算完；再配 Map 记频次，就变成 O(n)。
  5. 未使用的 pathArr：死变量，说明写到一半思路换了没清干净。

小结：暴力路径枚举想明白了，但 Medium 大数据会超时；本题标准升级就是 树上前缀和 + 哈希（同 560）。

最佳题解 ​

DFS 维护「根到当前」的前缀和，Map 记前缀出现次数（注意回溯删除）：

javascript
/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {number}
 */
var pathSum = function (root, targetSum) {
  const prefixCount = new Map([[0, 1]]);
  let ans = 0;

  function dfs(node, prefix) {
    if (!node) return;
    prefix += node.val;
    ans += prefixCount.get(prefix - targetSum) || 0;
    prefixCount.set(prefix, (prefixCount.get(prefix) || 0) + 1);
    dfs(node.left, prefix);
    dfs(node.right, prefix);
    prefixCount.set(prefix, prefixCount.get(prefix) - 1);
  }

  dfs(root, 0);
  return ans;
};
  • 时间 O(n)，空间 O(n)（深度 + Map）。
  • 为何更优：每个节点只做一次 O(1) 查询/更新；负数也适用；回溯保证不同分支不串频次。

若只求「从根到叶」则是 112；本题任意向下子路径，前缀差才是正解。

关联题目 ​

题为何相关
112. 路径总和必须根到叶，布尔版
113. 路径总和 II根到叶，要列出路径
560. 和为 K 的子数组同一前缀和 + 哈希，换到数组

一句话带走 ​

437 = 树上的 560：DFS 带前缀和，查 prefix - target，进出节点记得加减 Map。