Day 16 的刷题计划轮到 LeetCode 437 路径总和 III。说实话刚开始我有点轻敌前面刚把路径总和 I、II 都过了一遍觉得二叉树路径问题无非就是递归套递归用 JavaScript 写起来也不会难到哪里去。等我真正动手才发现这道题真正卡人的不是递归本身而是“路径可以不从根开始、也不用到叶子结束”这个条件再加上隐藏的复杂度陷阱。这篇文章就把我用 JavaScript 从暴力解到前缀和优化的完整过程、踩过的坑、以及能迁移到其他题型的思路一次讲清楚适合刚刷到二叉树路径问题、以及对复杂度优化还不太熟练的读者。1. 审题是第一关路径总和 III 和前面两道题到底差在哪1.1 模型从“根到叶子”变成“任意到任意”解题思路要跟着变路径总和 I 是经典的入门题判断二叉树中是否存在一条从根节点到叶子节点的路径使得路径上所有节点值的和等于 targetSum。路径总和 II 在此基础上加了一个要求不只要判断存在性还要把所有满足条件的路径完整打印出来。到了 437条件变成了给定一棵二叉树的根节点 root 和一个整数 targetSum返回节点值之和等于 targetSum 的路径数量。关键是后面这两句话路径不需要从根节点开始也不需要在叶子节点结束只要求从上往下走。我第一反应是“那不就是随便找一条向下的连续节点序列吗”但真正动手数的时候潜意识还是会往“从根出发”去靠。这个看似不起眼的认知差会让你漏掉路径也会让你在写代码时用错递归结构。1.2 先用官方示例把计数规则完整跑一遍官方给的示例树长这样10 / \ 5 -3 / \ \ 3 2 11 / \ \ 3 -2 1targetSum 8答案是 3。很多人看到答案的第一反应是数出 5 - 3 和 5 - 2 - 1 这两条然后就停了忘了 -3 - 11 这条也满足条件。为什么会漏因为在我们的思维习惯里树的遍历总是从根节点开始而 -3 这个节点藏在第二层需要先“绕过”根节点 10 才能看到它。如果我们默认路径必须包含根节点就会漏掉很多合法路径。手动数一遍会更清楚5 - 3和是 8命中5 - 2 - 1和是 8命中-3 - 11和是 8命中10 - -3 是 7差一点10 - 5 - 3 是 1810 - 5 - 2 - 1 是 18都超了单独节点 3、2、1、-2、10没有一个单独等于 8所以答案是 3 条。这道题的难点不在于求和而在于你要把每一个节点都当成可能的起点把每一个节点都当成可能的终点。1.3 向下路径本质上就是数组里的连续区间还有一个很关键的抽象一条从上到下的路径等价于一维数组中一段连续的区间。如果把“从根节点到某个节点”的累计和看作前缀和那么“从任意起点到任意终点”的区间和就等于终点前缀和减去起点前缀和。这个等价关系是后面所有优化的基石。数组里找连续子数组的和等于 K我们会想到用哈希表记录前缀和树上找连续路径的和等于 targetSum思路完全一样只不过遍历方式从线性变 DFS。2. 第一版暴力解双重递归先把正确性跑通2.1 暴力思路就是“把每个节点当起点”朴素做法很直接把每个节点都当作路径起点从该节点往下遍历累加路径和每次和 targetSum 相等就计数加一。这里天然需要两层递归外层递归遍历整棵树的所有节点让每个节点都有机会当起点内层递归从某个起点出发沿着左右子树往下走枚举所有可能的终点用 JavaScript 写出来是这样var pathSum function(root, targetSum) { if (!root) return 0; // 以固定节点 node 为起点向下的路径中有几条满足 sum targetSum const countFromNode (node, currentSum) { if (!node) return 0; currentSum node.val; let count 0; if (currentSum targetSum) count; count countFromNode(node.left, currentSum); count countFromNode(node.right, currentSum); return count; }; // 外层递归每个节点都当一次起点 return countFromNode(root, 0) pathSum(root.left, targetSum) pathSum(root.right, targetSum); };2.2 为什么外层递归写起来像“重复调用”刚开始我对外层这个写法有点绕pathSum已经是个递归函数里面竟然还调用了两个pathSum再加上一个countFromNode看起来像是重复计算。实际上它们分工不同。countFromNode(root, 0)只统计以 root 为起点的所有路径pathSum(root.left, targetSum)负责把 root.left 当成起点集合递归统计所有从 root.left 开始的路径pathSum(root.right, targetSum)同理。三个结果加起来才是“所有起点、所有终点”的全量答案。如果你还是觉得别扭可以把外层递归改成显式收集节点的方式逻辑会直白一些var pathSum function(root, targetSum) { let ans 0; const nodes []; const collect (node) { if (!node) return; nodes.push(node); collect(node.left); collect(node.right); }; collect(root); const dfsFrom (node, sum) { if (!node) return; sum node.val; if (sum targetSum) ans; dfsFrom(node.left, sum); dfsFrom(node.right, sum); }; nodes.forEach(node dfsFrom(node, 0)); return ans; };这种写法和第一种本质一样只是先把所有节点装进数组再逐个当起点去 DFS。我觉得它更适合理解“双重递归”的含义正式提交时用第一种更简洁。2.3 暴力解的复杂度最坏情况是 O(n²)分析复杂度要看最坏情况。假设这棵二叉树退化成一个链表每个节点只有一个孩子那么外层有 n 个起点每个起点往下延伸的路径长度分别是 n、n-1、n-2……1总操作次数是n (n-1) (n-2) ... 1 n * (n1) / 2 ≈ O(n²)n 到 5000 的时候这个量级大概是 1250 万次运算JavaScript 还能勉强跑n 到 10000 就是 5000 万次往上提交大概率会超时。当然 LeetCode 437 的官方测试数据不是全走极端链状树暴力解偶尔也能裸过但面试官如果追问一句“能不能优化”光会暴力解是站不住的。3. 前缀和 哈希表把 O(n²) 压缩成一次遍历3.1 核心公式终点前缀和减去起点前缀和等于 targetSum暴力解低效是因为同一个节点会被反复走很多遍。如果我们能在一次 DFS 过程中把已经走过的“从根到各祖先”的前缀和都记下来那就没必要每次从头累加。具体来说假设当前遍历到了节点 v从根到 v 的前缀和是 S。那么如果要找一条从某个祖先节点 u 到 v 的路径使得路径和等于 targetSum只需要满足S - S_u targetSum也就是S_u S - targetSum所以每到一个节点查一下哈希表里有没有出现过S - targetSum这个前缀和如果有就说明存在若干条以当前节点 v 为终点的合法路径数量就是哈希表里这个前缀和的次数。3.2 那个神秘的 map.set(0, 1) 到底是什么我第一次看别人题解的时候对map.set(0, 1)完全没概念后来才明白这是在模拟“路径起点之前的前缀和”。设想一下如果当前节点 v 恰好在根节点位置从根到 v 的前缀和 S 就是根节点的值。如果S - targetSum 0那么说明根节点到 v 的这段路径本身就是一条合法路径。哈希表里必须先有一个前缀和为 0 的记录才能让这种“从根开始的路径”被计数。value 1表示这个空前缀在路径开始之前已经出现了 1 次。它不代表一条真实路径只是让公式S_u S - targetSum在“起点是根节点”时也能成立。3.3 为什么 value 是出现次数而不是布尔值这是很多初学者容易忽略的细节。哈希表的 value 不只是“有没有”而是“出现过几次”。为什么需要考虑次数因为节点值有正数、负数、0所以在同一条路径上两个不同位置的前缀和可能完全相同。比如节点值序列是 3、-2、2从根开始的前缀和依次是 3、1、3同一个值 3 出现了两次。这两个位置作为路径起点时到当前节点的区间和可能不一样但只要它们前缀和相同用当前前缀和去减得到的区间和就是同一个 targetSum。换句话说前缀和相同的每个位置都能与当前节点构成一条独立合法路径所以必须全部计入。3.4 JavaScript 完整实现和回溯清理直接上代码var pathSum function(root, targetSum) { let count 0; const prefixMap new Map(); prefixMap.set(0, 1); const dfs (node, currentSum) { if (!node) return; currentSum node.val; // 当前路径上存在多少个前缀和使得 currentSum - prefix targetSum count prefixMap.get(currentSum - targetSum) || 0; // 把当前前缀和记录进去继续往下走 prefixMap.set(currentSum, (prefixMap.get(currentSum) || 0) 1); dfs(node.left, currentSum); dfs(node.right, currentSum); // 回溯还原现场防止左子树结果污染右子树 prefixMap.set(currentSum, prefixMap.get(currentSum) - 1); if (prefixMap.get(currentSum) 0) { prefixMap.delete(currentSum); } }; dfs(root, 0); return count; };这段代码我会拆成三块来讲因为每一块都有自己的坑。第一块是count prefixMap.get(currentSum - targetSum) || 0。在 JavaScript 里Map.get取不到值时会返回undefined不是0。如果不加|| 0count一旦加上undefined就会变成NaN整个提交就废了。这个错误特别隐蔽本地测试小用例大概率命中换一个数据集就炸。第二块是prefixMap.set(currentSum, ...) 1。一定要在当前节点完成判断之后再写入而不是先写入再判断。如果顺序反了当前节点自身也可能被当成“上一个节点”导致多算。保持“先查后写”的节奏是最稳的。第三块是回溯清理。DFS 从当前节点进入左子树时会往哈希表里累加左子树所有节点的前缀和。等左子树遍历完回到当前节点再进入右子树此时哈希表必须回到“只包含从根到当前节点这条路径上前缀和”的状态。如果没有把 currentSum 的计数减回去右子树就会误把左子树里的前缀和当作自己的祖先前缀和计数就会错乱。// 不清理的后果示例 // 左子树某个节点的前缀和是 8右子树遍历时去查 currentSum - targetSum // 结果查到了左子树留下的 8错误地认为右子树存在一条合法路径清理的写法就是把currentSum对应计数减一减到 0 就delete。这样两个兄弟子树之间完全隔离又不会影响祖先层级的记录。3.5 复杂度对比和实测感受前缀和版本每个节点只经过一次哈希表的查找和写入都是 O(1)总时间复杂度降到了 O(n)空间复杂度 O(n)。我拿一个深度很深的退化树用例实测过暴力解跑 3000 多毫秒前缀和版本只要 70 毫秒左右差距是肉眼可见的。在面试场景里你写出暴力解之后主动说一句“这题可以优化到 O(n)思路是用哈希表维护前缀和”然后当场写出来这是很加分的。因为 437 本身就是高频题很多人只会暴力能把前缀和思路讲清楚的人不多。4. 提交记录里的常见坑位边界、负数与大数4.1 空树和单节点的情况空树直接返回 0这个没什么好说的if (!root) return 0就已经覆盖了。单节点树要仔细一点。如果树里只有一个节点且它的值恰好等于 targetSum就返回 1否则返回 0。用前缀和版本自然能处理DFS 到唯一节点时currentSum 等于节点值然后去哈希表里查currentSum - targetSum查到了就计数查不到就返回 0。我建议读者在本地至少测这三个用例空树、单节点且命中、单节点不命中。别小看这些边角情况很多面试翻车都是栽在这种地方。4.2 有负数存在剪枝策略会失效路径总和 I 里如果节点值全是正数可以用“当前和已经超过 targetSum 就提前 return”来剪枝。但 437 明确说了节点值范围可以达到负值所以这种剪枝完全不能用。举个例子假设你在一条路径上累加到了 10targetSum 是 8看起来已经超了但后面如果接一个 -2 的节点总和马上变回 8照样是合法路径。所以唯一可靠的判断方式就是老老实实算前缀和差不要想着用大小比较来加速。这也是为什么前缀和版本在代码上并不比暴力复杂多少却更不容易出错的原因——它不需要依赖任何“数值单调”的假设。4.3 JavaScript 大数求和会不会有精度问题LeetCode 437 的节点值范围是 -10^9 到 10^9targetSum 也是这个量级二叉树的节点个数最多 1000 个。最极端情况下从根到某个叶子的路径和可能达到1000 * 10^9 10^12这个量级仍然远小于 JavaScript Number 的整数安全上限 2^53 - 1约 9 * 10^15所以直接用数字累加是没有精度风险的。如果你用其他语言做这题建议用 long 类型免得 int 溢出。JavaScript 反而不太需要担心这个问题。4.4 Map 相关的方法和选择做题的时候我见过有人用普通对象{}来记录前缀和不是不行但有两个隐患key 如果恰好是字符串__proto__这类特殊字符串对象的行为会变得诡异对象取值如果不存在会拿到undefined一样要处理默认值用Map更干净语义也更明确。而且Map对 key 的区分是基于值是否严格相等的不会像对象那样把数字 key 转成字符串所以用currentSum这种数字当 key 是最保险的。4.5 空路径会不会被误算还有个很多人会问的问题如果 targetSum 0会不会把“空路径”也算进去答案是不会。因为我们的代码只在访问到真实节点时执行count prefixMap.get(currentSum - targetSum)不存在“不选任何节点”这种情况。prefixMap.set(0, 1)只是为了让从根开始的路径在公式上成立并不会在答案里额外加一条空路径。5. 由一道题看一类题前缀和在数组和树上的迁移5.1 和 LeetCode 560 子数组和等于 K 的关系如果你刷过 LeetCode 560你会发现 437 的解法几乎就是它的“树版本”。560 是给一个数组 nums 和一个整数 k返回连续子数组中满足和为 k 的子数组个数。它的经典解法也是维护一个prefixMap遍历数组时计算前缀和然后count prefixMap.get(currentSum - k)再把当前前缀和写进哈希表。437 只是把“从左到右遍历数组”换成了“从根到叶子递归遍历树”DFS 天然保证了路径的上下顺序。唯一多出来的步骤是回溯清理因为树有多个分支数组只有一条序列数组不需要想着清理状态树必须清理。所以我在刷题时会刻意把这两道题放在一起复习。它们共享同一个核心模型前缀和 哈希表。理解了这个模型你看到“连续区间 和等于目标值”的描述第一反应就知道该用什么套路而不是每道题从头推理。5.2 和二叉树路径家族题的横向对比437 属于“树上路径”这个大家族。我拿几个高频题放在一起比较题目路径起点路径终点求解目标常用方法路径总和 I根节点叶子节点是否存在简单递归路径总和 II根节点叶子节点打印所有路径递归 回溯路径总和 III任意节点任意节点计数所有路径前缀和 哈希表二叉树最大路径和任意节点任意节点最大路径和后序递归二叉树直径任意节点任意节点最长路径长度后序递归 深度统计这样列出来你会发现每道题的区别其实就三点起点约束、终点约束、答案口径。审题时把这三点想清楚解题方向基本就定了。5.3 刷题节奏上的个人建议Day 16 这个进度我个人的体会是碰到这种有好几种解法的题不要只背最优解而是先暴力、再优化、最后对比复杂度。第一遍写暴力能帮你彻底理解题意第二遍写前缀和能帮你建立“空间换时间”的感觉第三遍如果还有时间可以尝试用迭代栈实现一次 DFS加深对递归栈模型的理解。我当时就是第一天先交暴力版跑通第二天再重写前缀和版第三天把迭代版本过了一遍。这种分阶段的学习方式比一次就把所有知识点塞进脑子里要扎实得多。这道题还可以继续扩展如果把题目改成“输出所有和为 targetSum 的路径”你可以把前缀和哈希表从Map换成Mapnumber, array每个前缀和记录对应的节点指针回溯时一边收集路径、一边删掉已处理的分支。想看更难的版本也可以去看看 LeetCode 124它同样允许任意起点任意终点但求的是最大路径和方法完全不同。每道题做透之后再往边界延伸一点刷题的价值会比单纯过题高很多。