手帐 Blog

主题

复盘 · LC 437 路径总和 III（二刷） ​

题目 ​

题意 ​

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

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

边界：空树；单节点；负数（本地测例 targetSum = -1）；同一前缀多次出现。

涉及算法 ​

标签一句话
前缀和 + 哈希ans += count(prefix - target)，与 560 同构
DFS + 回溯进节点加频次、出节点减频次，避免左右子树串频次

教程对照：08 · 前缀和、17 · 二叉树递归经典。首刷对照：8/13 · 437。

评价我的解法 ​

相对昨天路径数组暴力枚举 118/130 TLE，今天直接默写「树上 560」——二刷升级成功，AC（约 3ms / 60.5MB，击败约 79%）。

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

javascript
var pathSum = function (root, targetSum) {
  const map = new Map([[0, 1]]);
  let res = 0;
  function dfs(root, prefix) {
    if (!root) {
      return;
    }
    prefix = prefix + root.val;
    res += map.get(prefix - targetSum) || 0;
    map.set(prefix, (map.get(prefix) || 0) + 1);
    dfs(root.left, prefix);
    dfs(root.right, prefix);
    map.set(prefix, (map.get(prefix) || 0) - 1);
  }
  dfs(root, 0);
  return res;
};

评价：

  1. 模板齐：Map([[0, 1]])、先查 prefix - target 再写入、左右 DFS、回溯 -1——四件套齐全。
  2. 复杂度到位：每节点 O(1) 查改 → 整树 O(n)，空间 O(h + 不同前缀数)。
  3. 负数意识：本地用 1 / -2 / -3、target = -1 自测，说明知道前缀差对负数也成立。
  4. 可打磨：参数名与外层同叫 root 略糊；回溯时频次减到 0 可不删（功能正确）；命名 prefixCount / ans 更利于口述。

小结：从 O(depth²) 枚举切到前缀哈希，把昨天复盘里的「最佳题解」真正变成自己的默写。

最佳题解 ​

与今日写法同构，仅命名更清晰：

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 操作；回溯保证路径互不污染。

关联题目 ​

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

一句话带走 ​

437 二刷口诀：树上 560——查 prefix - target，进加出减。