尧图网页设计 
最近几个技术群里又聊到了 LeetCode 的 Hot 100提到 437 题“路径总和 III”时好些人都说这道题“看着不难一写就废”。确实这题明面上是个二叉树遍历题干里连个复杂数据结构都没提可它在 Hot 100 里却是少有的“需要一点思维拐弯”的题目。我刷了这么多遍越来越觉得这题特别适合拿来练两个东西一个是对前缀和的理解另一个是递归回溯时对状态的管理。很多人面试栽在这道题上不是不会写 DFS而是漏了“路径可以不从根开始、也不到叶子结束”这个条件导致算法和代码都没踩到点子上。这篇文章我打算把这题从头到尾彻底掰开讲一遍包括题目到底在问什么、为什么暴力解不建议用、前缀和优化的核心思路是什么、三种主流语言的实现怎么写以及我在实际调试中踩过的几个坑。内容会比较长但每一步都会配上思路说明保证你读完能自己手写出来也能把“路径计数 前缀和 回溯”这套组合拳用到别的题目里。1. 题目深度拆解——先搞懂它在问什么很多人在 LeetCode 上看到 437 题的第一反应是这不就是遍历树嘛算路径总和嘛二叉树的路径总和 I 和 II 都会做这题还能难到哪去结果一提交就发现事情没这么简单。这里最大的认知差异在于“路径总和 III”里说的路径和前面两道题完全不是一回事。1.1 题目到底在问什么原题描述是给定一个二叉树的根节点 root和一个整数 targetSum求这棵树里路径和等于 targetSum 的路径总数。路径的定义是从树中任意节点出发沿着父节点指向子节点的方向到达任意节点结束路径上的节点值之和为 targetSum。路径不需要从根节点开始也不需要到叶子节点结束但必须是向下走的。这句话里有三个关键限定条件方向固定只能从上往下走不能回头不能横跳。起点不固定可以从任意节点开始不只是根节点。终点不固定可以在任意节点结束不要求是叶子。举个最简单的例子如果一棵树是一条直线 1 → 2 → 3targetSum 3那么满足条件的路径就有两条一条是从根节点 1 走到节点 2路径和为 3另一条是单独从节点 3 开始自己就是 3。这两条路径的起点、终点都不同但都算数。理解了这三个条件才能真正明白为什么后面要用前缀和来解。因为“起点不固定终点不固定”意味着你不能只维护“从根到当前节点”的路径和然后判断是否等于 targetSum那样只覆盖了从根节点出发的情况。你要做的是对于每一个当前节点找到它上方所有可能的起点只要从某个起点到当前节点的路径和等于 targetSum这条路径就符合要求。1.2 和其他“路径总和”题目的区别把这三道题放一起看你就能发现 LeetCode 的出题思路是非常有层次的路径总和 I判定是否存在一条从根节点到叶子节点的路径路径和等于 targetSum。这道题只需要 DFS 时记录累计和走到叶子节点判断一次即可。路径总和 II找到所有从根节点到叶子节点、路径和等于 targetSum 的路径并且要输出具体的路径节点序列。这需要 DFS 回溯维护一个路径列表。路径总和 III统计所有从上到下、任意起点到任意终点的路径数量路径和等于 targetSum。既不要求从根开始也不要求到叶子结束只统计数量不要求输出具体路径。第 III 题和前面两题最大的不同就是“任意起点”这个解放。如果还是用根到叶子的思路你会发现你漏掉了大量从中间节点开始的路径。比如一棵树的根节点是 10左子树是 5 → 3targetSum 8那么 5 → 3 这条路径是满足的但根节点根本不在这条路径上。如果你只从根出发做 DFS就会把这条路径漏掉。1.3 暴力解法的思路和局限第一次看到这道题大多数人的直觉是遍历每个节点把每个节点都当作起点往下 DFS 找路径和等于 targetSum 的路径数量。这就是所谓的“双重 DFS”外层遍历所有节点内层从当前节点出发往下搜索。伪代码如下int pathSum(TreeNode root, int targetSum) { if (root null) return 0; int count dfs(root, targetSum); // 以 root 为起点往下找 count pathSum(root.left, targetSum); // 递归处理左子树 count pathSum(root.right, targetSum); // 递归处理右子树 return count; } int dfs(TreeNode node, long curSum) { if (node null) return 0; int count 0; curSum - node.val; if (curSum 0) count; count dfs(node.left, curSum); count dfs(node.right, curSum); return count; }注意这里我用了一个小技巧把“路径和等于 targetSum”转化为“targetSum 减去路径上节点值之和等于 0”这样就不用额外维护累计和参数了。暴力解的时间复杂度是 O(n²)其中 n 是节点数。对于类似一条链的极端情况每个节点都要往下遍历剩余的所有节点复杂度会逼近 O(n²)。在 LeetCode 的测试数据下这个复杂度的代码通常也能通过因为二叉树的平均深度不高但如果你刷题只是“求过”你很容易被这种通过率误导。真正的面试官在追问“你的解法时间复杂度是多少”时如果你只能答出 O(n²)那这题的得分会打折扣。更重要的是暴力解里隐藏着一个很容易写错的地方外层递归和内层 DFS 的“职责”要分开。外层负责枚举起点内层负责从起点往下统计可行路径两者不能混。很多人在写的时候把“以当前节点为起点往下找”和“继续往子树递归”混在一个函数里导致路径数量算重复或者漏算。我自己刚开始刷这道题时就是这样写出来的代码跑测试用例能过一提交就差那么一两个用例。后来调试才发现是外层递归把当前节点往下的路径数重复计入了。所以如果要用暴力解建议把“寻找所有起点”和“从起点往下统计”拆成两个职责明确的函数别图省事合成一个。2. 前缀和优化——把树上的路径问题变成数组上的数学问题暴力解虽然能过但作为追求更优解的工程师肯定要往下想一步能不能在线性时间内解决能关键就在前缀和。2.1 前缀和在一维数组上的经典用法先回到一维数组的场景。给定一个整数数组 nums和一个目标值 k统计有多少个连续子数组的和等于 k。经典解法就是用前缀和加哈希表设 prefixSum[i] 表示 nums[0] 到 nums[i] 的前缀和那么子数组 nums[j1] 到 nums[i] 的和就等于 prefixSum[i] - prefixSum[j]。要找和为 k 的连续子数组就是找有多少对 i 和 j使得 prefixSum[i] - prefixSum[j] k等价于 prefixSum[j] prefixSum[i] - k。所以在遍历到第 i 个元素时只需要知道前面有多少个 prefixSum 等于 prefixSum[i] - k就能一次性统计出所有以 i 结尾的、和为 k 的子数组数量。用哈希表记录每种前缀和出现的次数查询是 O(1) 的整体时间复杂度降到了 O(n)。这个思想的核心是把“连续区间和等于 k”转化成“两个前缀和之差等于 k”用空间换时间。2.2 如何把前缀和“嫁接”到二叉树上二叉树和数组最大的区别在于数组是线性结构每个位置只有一个前驱二叉树是分支结构每个节点有左右两个后继。但如果你只看“从根到当前节点的路径”那么这条路径就是一个线性序列完全可以用前缀和来思考。定义从根节点到当前节点 p 的路径上所有节点值的和为 currSum。那么对于当前节点 p我们想知道的是在这条路径上有多少个节点 qq 在根和 p 之间包含根不包含 p使得从 q 到 p 的路径和等于 targetSum。从 q 到 p 的路径和 currSum - sumFromRootToParentOfQ。翻译成前缀和的语言就是我们要找在这条路径上是否存在某个前缀和 pre使得 currSum - pre targetSum也就是 pre currSum - targetSum。如果这条路径上某个前缀和 pre 出现了 cnt 次那么以当前节点 p 为终点、和为 targetSum 的路径就有 cnt 条。这个逻辑完全沿用了数组子数组求和的做法。但树和数组有一个非常大的区别数组的前缀和是“全局”的而树上的前缀和是“路径相关”的一条从根到左子树的路径和一条从根到右子树的路径它们各自的前缀和序列是独立的。你不能像数组那样从第一个元素一直扫到最后一个元素来维护一个单调的前缀和集合。这就引出了解决这道题最关键的操作回溯时恢复现场。当你从当前节点递归进入左子树时当前节点的前缀和应该保持在哈希表里递归进入右子树时也应该保持。但当左子树递归结束要回到当前节点、再进入右子树时你必须把刚才在左子树里新增的前缀和记录删掉否则右子树的路径统计会错误地使用到左子树的前缀和信息。这一点我在初学的时候想了好久才绕明白哈希表里如果残留了左子树某个节点的前缀和信息那么在当前节点的右子树里判断“某个前缀和出现了多少次”时会把左子树里那些不相干的路径也算进来导致结果偏大。2.3 状态管理的本质哈希表维护的到底是什么把哈希表 前缀和的方案理清楚核心就两个问题一、哈希表里存的 key 是什么是“从根到某个节点的路径上的节点值总和”也就是路径前缀和。二、哈希表里存的 value 是什么是“在当前递归路径上该前缀和出现了多少次”。注意“当前递归路径”这几个字它不是一个全局的概念而是随着 DFS 的推进不断变化的。为了更好理解可以用一个生活化的类比。假设你在一个迷宫里每经过一个路口你就在本子上记一笔“从入口到这里的累积里程”。当你站在某个位置时你想知道有没有一条从之前的某个路口到这里的路程刚好等于 targetSum你只需要拿当前累积里程减去 targetSum看看这个差值在之前的记录里出现过没有。这个本子就是哈希表。但是迷宫是分叉的。你从入口出发走了一条岔路到底折返回来再走另一条岔路。当你在第二条岔路里查看本子时你绝不应该把第一条岔路里的记录也算进来。这就要你在折返时把第一条岔路新记的内容擦掉。DFS 回溯时的 map.remove 操作干的就是这个“擦掉”的活儿。理解了这一点你就掌握了这类“在树/图上做前缀和计数”问题的全局视角。后面不管遇到二叉树、还是更复杂的图结构只要能在搜索路径上维护状态、在回溯时恢复基本都能套用这套思想。2.4 时间复杂度分析O(n) 是怎么来的用了前缀和 哈希表之后每个节点只被访问一次。每次访问时哈希表的查询和插入操作均摊复杂度都是 O(1)所以整体时间复杂度是 O(n)n 为树中节点数。空间复杂度方面递归栈深度决定了额外空间的上限。最坏情况下如果树是一条链递归深度是 n此时空间复杂度是 O(n)。平均情况下二叉树的深度是 O(logn)空间复杂度也就是 O(logn)。所以从复杂度角度前缀和方案和暴力方案是质的差别一个是线性扫描一个是近似平方级。面试的时候如果能从暴力解过渡到前缀和解法并且把复杂度分析讲清楚这题基本就稳了。3. 核心代码实现——三种语言对照逐行拆解关键细节光讲理论不动手是记不住的。这一节我会给出 Java、C、Python 三种语言的完整实现并对每个关键分支做注释。这三种语言的代码思路完全一样区别只是语法细节和类型处理。3.1 Java 实现用 Map 记录路径前缀和import java.util.HashMap; import java.util.Map; class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val val; this.left left; this.right right; } } class Solution { public int pathSum(TreeNode root, int targetSum) { // key前缀和value出现次数 MapLong, Integer prefixSumCount new HashMap(); // 初始化前缀和为 0 的路径有 1 条即不选任何节点 prefixSumCount.put(0L, 1); return dfs(root, 0L, targetSum, prefixSumCount); } private int dfs(TreeNode node, long currentSum, int targetSum, MapLong, Integer prefixSumCount) { if (node null) { return 0; } currentSum node.val; // 核心找出从某个祖先到当前节点路径和为 targetSum 的路径数量 long target currentSum - targetSum; int count prefixSumCount.getOrDefault(target, 0); // 将当前前缀和加入哈希表继续往下递归 prefixSumCount.put(currentSum, prefixSumCount.getOrDefault(currentSum, 0) 1); count dfs(node.left, currentSum, targetSum, prefixSumCount); count dfs(node.right, currentSum, targetSum, prefixSumCount); // 回溯恢复现场避免当前路径信息影响兄弟子树 prefixSumCount.put(currentSum, prefixSumCount.get(currentSum) - 1); if (prefixSumCount.get(currentSum) 0) { prefixSumCount.remove(currentSum); } return count; } }这里有个容易忽略的细节prefixSumCount.put(0L, 1)这一行。它表示“前缀和为 0 的路径存在 1 条”也就是从根节点出发的位置。为什么要初始化它因为如果从根节点到当前节点的累计和 currentSum 恰好等于 targetSum那么查找 currentSum - targetSum 0 时需要能查到 1 条记录这正是“从根节点出发的路径”被统计进去的关键。Java 语言里还有一个小坑树节点的 val 可能是负数targetSum 也可能是负数所以 currentSum 用long类型比较安全。当 targetSum 很大或节点值很极端时int 累加可能会溢出。虽然 LeetCode 的测试数据一般不触发这个边界但在实际工程里写代码尤其是处理累加和的场景用 long 是更稳妥的习惯。3.2 C 实现同样的思路更精简的表达#include unordered_map struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} }; class Solution { public: int pathSum(TreeNode* root, int targetSum) { unordered_maplong long, int prefixSumCount; prefixSumCount[0] 1; return dfs(root, 0LL, targetSum, prefixSumCount); } private: int dfs(TreeNode* node, long long currentSum, int targetSum, unordered_maplong long, int prefixSumCount) { if (node nullptr) { return 0; } currentSum node-val; long long target currentSum - targetSum; int count prefixSumCount.count(target) ? prefixSumCount[target] : 0; prefixSumCount[currentSum]; count dfs(node-left, currentSum, targetSum, prefixSumCount); count dfs(node-right, currentSum, targetSum, prefixSumCount); // 回溯恢复 prefixSumCount[currentSum]--; if (prefixSumCount[currentSum] 0) { prefixSumCount.erase(currentSum); } return count; } };C 版本和 Java 版本结构基本一致。有一个细节是prefixSumCount[currentSum]这一行会让不存在的 key 自动初始化为 0然后加 1。这看起来很简洁但需要注意 implicit 构造会引入默认值如果你在递归里频繁这样做哈希表的 size 可能会略微增大不过复杂度还是 O(n)问题不大。我个人的习惯是尽量少用这种隐式方式而是写成prefixSumCount[currentSum] prefixSumCount.count(currentSum) 0 ? 1 : prefixSumCount[currentSum] 1;虽然啰嗦一点但逻辑清楚面试时口述代码也不容易绕晕。3.3 Python 实现代码最短但要注意引用传递class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right class Solution: def pathSum(self, root: TreeNode, targetSum: int) - int: from collections import defaultdict prefixSumCount defaultdict(int) prefixSumCount[0] 1 def dfs(node: TreeNode, currentSum: int) - int: if not node: return 0 currentSum node.val target currentSum - targetSum count prefixSumCount.get(target, 0) prefixSumCount[currentSum] 1 count dfs(node.left, currentSum) count dfs(node.right, currentSum) # 回溯恢复 prefixSumCount[currentSum] - 1 if prefixSumCount[currentSum] 0: del prefixSumCount[currentSum] return count return dfs(root, 0)Python 的defaultdict在这里非常方便访问不存在的 key 会自动返回默认值。但要注意prefixSumCount[currentSum] - 1之后如果次数减到 0最好手动del掉这个 key。否则你可能会在后续路径上把“没出现过的前缀和”误认为出现了 0 次虽然结果一样查询时查到 0 和查不到都返回 0但哈希表的 size 会一直增长而且逻辑上不够干净。Python 递归里的 inner function 可以直接引用外部的 prefixSumCount 和 targetSum不需要像 Java、C 那样显式传参。但要注意 Python 默认递归深度限制是 1000如果题目的树的深度特别深比如一条 1000 层以上的链递归会爆栈。LeetCode 上这道题的测试数据一般不会触发这个限制但你在本地自己构造极端测试用例时得注意这一点。3.4 核心代码的五个关键细节分析完三种实现我强烈建议你把下面这五个细节刻在脑子里因为面试官常常在这五个点上追问第一初始化map[0] 1是干什么的回答为了让从根节点出发的合法路径能被统计到。如果一棵树根节点的 val 正好等于 targetSum当前 currentSum - targetSum 0此时需要查到这个 0 的记录存在路径数才能加 1。第二为什么在递归进入左右子树之前要把当前前缀和放入哈希表回答因为我们要统计的是“以当前节点为终点的路径”所以要保证从根到当前节点路径上的所有前缀和都记录在案这样后续的节点在以祖先为起点判断时才能正确查到对应的前缀和差值。第三为什么回溯时要删掉或减掉当前前缀和的次数回答因为二叉树的路径是分叉的我们不想让左子树的节点前缀和信息影响右子树的路径统计。这正是“路径独立性”的要求也是前缀和方案区别于数组方案的核心差异。第四currentSum为什么用 long 类型回答避免极端情况下 int 溢出。一个树深 1000 层、每层节点值都是 10^9 级别的链累计和会轻松超过 int 范围导致结果错误。第五为什么用getOrDefault而不是直接map.get回答因为哈希表里可能不存在目标前缀和直接get会返回 null在拆箱时触发空指针异常。无论是 Java 还是其他语言查询不存在的 key 都要做容错。4. 实操中的常见问题与排查经验——刷了几遍之后总结的避坑清单这道题在 LeetCode 里提交过多少次出现过多少种奇奇怪怪的错误恐怕比题目本身还精彩。我把我自己做题时遇到的、以及在评论区看到的典型问题做了个汇总分成几个类别来聊。4.1 “int 传递导致路径计数丢失”的问题很多初学者在写递归时会把 count 作为参数传递下去像这样int count 0; dfs(root, targetSum, count); // 错误示范然后发现 count 永远是 0。原因在于 Java 和 C 这类语言的函数参数传递基本类型是值传递你在子递归里对 count 的修改不会影响外层变量的值。所以要么用返回值累加要么把 count 放进一个数组或自定义对象里。上面给的三种语言实现全都采用返回值累加的方式这是最清晰、最不容易出错的做法。还有一种做法是把 count 作为类成员变量全局累加。这也能跑通但会导致递归函数之间共享状态如果这道题要在多组测试数据之间复用同一个 Solution 实例就很可能出现“上一次的结果残留”的 bug。我建议在面试时统一用返回值方案。4.2 “前缀和计数减到 0 但不删除 key”的隐患在我的经验里很多正确解法里只写prefixSumCount[currentSum]--但减到 0 后不删除 key。这在 LeetCode 上不会导致 WA因为查询时查到 0 和查不到都返回 0结果正确。但如果哈希表的 size 一直增大在极端构造下可能出现内存增长的问题而且逻辑上也不够清晰。更重要的是在某些变体题目里比如要求输出具体路径如果哈希表里残留了大量次数为 0 的 key会干扰后续对“是否存在这个前缀和”的判断。为避免后续可变性我的习惯是当次数减到 0 时直接删除 key。代价是一个if判断几乎可以忽略但换来的是哈希表始终保持只包含当前路径上真实存在的前缀和调试时看 map 的内容也一目了然。4.3 “漏掉负数导致前缀和查询出错”的认知误区有些人在做这道题时总觉得前缀和一定单调递增所以在查找差值时只往前找忽略了可能有负数的情况。但实际上这棵树的节点值可以是负数targetSum 也可以是负数所以前缀和序列并不是单调的。不过好消息是哈希表方案天然不依赖单调性。不管前缀和是增是减只要哈希表里的记录是准确的查询 currentSum - targetSum 永远是对的。这反而是前缀和方案比滑动窗口方案优势更大的地方。滑动窗口要求区间和单调不能处理负数而前缀和 哈希表完全不在乎值的正负。我在给初学的人讲这道题时一定会强调这一点哈希表方案之所以鲁棒是因为它把问题转化成了“两个前缀和的差值是否等于 target”而不是“边加边判断往哪边走”。后者在二叉树这种分支结构里根本不可行前者才是真正的线性做法。4.4 “空节点进入递归导致重复计数”的坑树的问题里空节点null处理是最容易写错的地方。常见的做法有两种第一种是在 dfs 开头判断if (node null) return 0。这样写很简单但要注意空节点不会产生任何路径计数也不会改变 currentSum返回 0 即可。第二种在调用 dfs 之前先判断子节点是否为空只在非空时才递归if (node.left ! null) { count dfs(node.left, currentSum, targetSum, prefixSumCount); }两种写法效果一样。我个人的习惯是统一在函数开头判断空节点这样可以少写几个if也不容易漏掉分支。但要注意如果采用了开头判断空节点的写法那对于空节点一定不要执行任何哈希表操作否则会把一个“虚拟的前缀和”记录进哈希表污染路径统计。4.5 调试技巧用小规模树验证中间状态如果代码跑出来结果不对我强烈建议别直接对着大测试数据瞎找原因而是构造一个小树手动模拟递归过程打印每一步的 currentSum 和哈希表内容。比如一个很经典的测试用例root [10, 5, -3, 3, 2, null, 11, 3, -2, null, 1], targetSum 8答案是 3。怎么算出来的三条路径分别是5 → 35 → 2 → 1-3 → 11。你可以在递归里加一个调试打印System.out.println(currentSum currentSum , target (currentSum - targetSum) , map prefixSumCount);这样就能观察到每个节点处哈希表到底存了什么也就能直观看到回溯删除 key 前后的变化。真正理解了 map 里的内容如何“随路径伸缩”这道题才算真会了。还有一个我常用的自测方法把暴力解和前缀和解同时跑一遍对随机生成的小规模二叉树节点数量 10 到 20 个值在 -5 到 5 随机对比两者的结果是否一致。如果一致大概率说明前缀和解法逻辑正确如果不一致就用小树 打印定位问题。这个方法我在刷很多二叉树题时都用效率非常高。4.6 常见错误速查表错误类型具体表现原因解决方案路径计数丢失结果始终为 0count 作为基本类型参数传递使用返回值累加或成员变量/引用类型结果偏大比预期多出几条路径遍历完左子树后没有回溯删除左子树的前缀和记录递归返回前将当前前缀和计数减 1减到 0 则删除空指针异常运行时报 NullPointer查询不存在的 key 时直接 intValue使用 getOrDefault或先判断 key 是否存在溢出大值测试下输出错误currentSum 使用 int 类型累加溢出使用 long 类型保存前缀和重复计数同一路径被统计多次外层遍历所有节点时内层 DFS 又重复包含起点节点自身明确区分“枚举起点”和“从起点出发统计”的职责结果偏小从根出发的路径未被统计没有初始化 map[0] 1在递归开始时手动插入 0 的计数这张表我建议收藏起来以后写任何“树 路径 前缀和”的题目时都能参考。你会发现很多类似的题目比如统计路径总和等于 target 的具体路径条数、最长路径和等本质上都是这几个坑的变体。5. 从 437 题看到的一类题目套路——前缀和在树上的扩展这道题做完如果不总结套路那是很大的浪费。437 题的价值不只在它本身更在于它展示了“前缀和”这种数据结构在树形结构上的一种应用范式。我用了不少时间把这类题目串起来看发现它们的共同点可以用一句话概括在一条根到节点的路径上寻找满足某种“区间差值条件”的节点对。5.1 变体题求和为 target 的最长路径长度有个很经典的变体题是二叉树中求所有路径中路径和等于 targetSum 的最长路径长度。路径的定义和 437 题一样可以任意起点、任意终点但要求向下。这道题可以用同样的前缀和思路但哈希表里存的就不只是“前缀和出现了几次”而是“前缀和最早出现在哪一层”。在遍历时对于当前节点如果 currentSum - targetSum 之前已经出现过那么路径长度就是当前层数减去历史层数。为了求最长路径记录最早出现的层数即可。这道题的代码几乎和 437 题同构唯一的区别就是 map 的 value 从 count 变成了 depth以及递归返回时需要把 map 恢复到进入节点之前的状态。学了 437 题再去写这个变体基本相当于换汤不换药。5.2 变体题路径总和 II 的输出形式扩展另一类变体是要求输出具体的路径节点序列不只是数量。这时前缀和哈希表方案就不够用了因为你虽然能快速知道存在多少条路径却无法直接回溯出路径上的具体节点。这类题通常是暴力 DFS 回溯时维护 path 列表或者用哈希表存的 value 更复杂一些。但从底层思维来说都是“路径状态 回溯”。这也是为什么我一直建议刷题时不要死记代码模板而要掌握“路径上维护状态信息、回溯时恢复状态”这个元方法。437 题就是最好的题源因为它把这种方法压缩在一段不到 30 行的代码里。5.3 从一道题迁移到一类题总结属于自己的模板我自己的习惯是每做完一道有代表性的题就把它的框架抽取成模板。以 437 题为例我能抽象出的模板是初始化哈希表记录基础状态 定义递归函数(node, 当前状态, 目标条件): if node 为空: 返回默认值 更新当前状态 根据 当前状态 和目标条件从哈希表里查询需要的信息累加到结果 将当前状态写入哈希表 递归处理子树汇总结果 回溯将当前状态从哈希表移除/恢复 返回结果这个模板适用于三类题目统计路径满足某种条件的数量437 题求路径满足某种条件的极值长度最长路径和等于 target判断是否存在满足条件的路径路径总和 I / II 的变体把模板用熟了你在面试中看到“二叉树 路径 和/差/最长/数量”这些字眼时就不会一头雾水而是能快速判断“这是不是要我维护路径前缀和然后在递归过程中查询差值”5.4 刷题之外的工程意义可能有人说这题在工程上能用到哪其实真有用。树形结构在前端组件树、文件目录树、组织架构树里都很常见。比如一个常见的需求给定一个目录树统计所有子目录的大小之和等于某个值的路径数量或者是组织架构里统计某个职级以下的团队人力总和满足条件的汇报链。虽然业务系统里不会真有 targetSum 这种直白的概念但“在树路径上做区间聚合统计”这件事情底层用的也是同样的遍历和状态管理思路。更重要的是前缀和思想本身维护累计值 哈希表查询历史在流式数据处理、数组区间查询、股票收益计算等场景都非常常见。437 题只是把这个思想放到了树上。所以刷这一道题学到的不只是一个题解而是一种可以迁移到多个领域的建模能力。6. 复盘与思考——我消化 437 题的方式最后这部分就不列代码了聊点我个人的“消化过程”。这题我前后刷了可能得有五六遍每一遍感觉都不一样。第一遍是照着暴力解代码抄过了第二遍是看前缀和解法能读懂但自己写还是漏回溯第三遍能独立写出来但被面试官一追问复杂度就卡壳到后面几遍才开始真正理解“为什么要在递归返回前恢复哈希表”这个动作而不是机械地记忆代码。如果你现在正处于“照着题解能写自己写就卡”的阶段我的建议是不要急着背解法而是把每一行代码都问一个为什么。为什么map.put(0, 1)因为根节点路径需要被统计。为什么在递归子树之前把当前前缀和放进去因为后续节点要把它当作可能的起点。为什么递归返回时要恢复现场因为每条根到叶子路径是独立的。把这几个问题想通了你会发现这类题后面的逻辑是顺下来的根本不需要死记硬背。哪怕有一天你忘了具体代码只要还记得“前缀和 哈希表 回溯恢复现场”这个组合你就能在面试现场把代码重新推导出来。另外437 题在 Hot 100 里的热门程度本身也说明了它的价值。Hot 100 的题目筛选是有讲究的它既要覆盖高频面试考点也要涵盖不同难度梯度和思想类型。437 题之所以入选大概率就是因为它用最朴素的二叉树场景考察了“前缀和 递归 回溯”这几个算法基础元素是一个相当综合的训练场。如果你正在刷 Hot 100我个人的刷题顺序建议是把二叉树相关的题目放到一起刷比如 104、112、113、437 这几道放一起先做简单的求深度、判定路径和再做输出路径最后做任意起点终点计数。这样由浅入深你对“路径”这个概念的理解会比单刷任何一道题都要深刻得多。我把这题放在个人博客里当成一个“树 路径问题的代表题”来复盘每次重读自己写过的分析都还能发现新的细节。这也是我为什么推荐你在刷题之余用自己的话把题解思路写一遍。写作是很好的思维整理工具当你发现自己能在不对照代码的情况下把“为什么”讲清楚时这题才算真正属于你了。最后再分享一个小技巧如果面试时时间紧张先把暴力解的思路说清楚再提出可以用前缀和优化。这么做有两个好处一是向面试官展示你具备从低效到高效的优化意识二是就算最后代码没写完你已经展示了自己的思路层级面试官通常也会给一个不错的评价。写代码之前先把话说清楚往往比闷头写代码更让面试官放心。 LeetCode 437 路径总和 III：前缀和与回溯解法剖析
最近几个技术群里又聊到了 LeetCode 的 Hot 100提到 437 题“路径总和 III”时好些人都说这道题“看着不难一写就废”。确实这题明面上是个二叉树遍历题干里连个复杂数据结构都没提可它在 Hot 100 里却是少有的“需要一点思维拐弯”的题目。我刷了这么多遍越来越觉得这题特别适合拿来练两个东西一个是对前缀和的理解另一个是递归回溯时对状态的管理。很多人面试栽在这道题上不是不会写 DFS而是漏了“路径可以不从根开始、也不到叶子结束”这个条件导致算法和代码都没踩到点子上。这篇文章我打算把这题从头到尾彻底掰开讲一遍包括题目到底在问什么、为什么暴力解不建议用、前缀和优化的核心思路是什么、三种主流语言的实现怎么写以及我在实际调试中踩过的几个坑。内容会比较长但每一步都会配上思路说明保证你读完能自己手写出来也能把“路径计数 前缀和 回溯”这套组合拳用到别的题目里。1. 题目深度拆解——先搞懂它在问什么很多人在 LeetCode 上看到 437 题的第一反应是这不就是遍历树嘛算路径总和嘛二叉树的路径总和 I 和 II 都会做这题还能难到哪去结果一提交就发现事情没这么简单。这里最大的认知差异在于“路径总和 III”里说的路径和前面两道题完全不是一回事。1.1 题目到底在问什么原题描述是给定一个二叉树的根节点 root和一个整数 targetSum求这棵树里路径和等于 targetSum 的路径总数。路径的定义是从树中任意节点出发沿着父节点指向子节点的方向到达任意节点结束路径上的节点值之和为 targetSum。路径不需要从根节点开始也不需要到叶子节点结束但必须是向下走的。这句话里有三个关键限定条件方向固定只能从上往下走不能回头不能横跳。起点不固定可以从任意节点开始不只是根节点。终点不固定可以在任意节点结束不要求是叶子。举个最简单的例子如果一棵树是一条直线 1 → 2 → 3targetSum 3那么满足条件的路径就有两条一条是从根节点 1 走到节点 2路径和为 3另一条是单独从节点 3 开始自己就是 3。这两条路径的起点、终点都不同但都算数。理解了这三个条件才能真正明白为什么后面要用前缀和来解。因为“起点不固定终点不固定”意味着你不能只维护“从根到当前节点”的路径和然后判断是否等于 targetSum那样只覆盖了从根节点出发的情况。你要做的是对于每一个当前节点找到它上方所有可能的起点只要从某个起点到当前节点的路径和等于 targetSum这条路径就符合要求。1.2 和其他“路径总和”题目的区别把这三道题放一起看你就能发现 LeetCode 的出题思路是非常有层次的路径总和 I判定是否存在一条从根节点到叶子节点的路径路径和等于 targetSum。这道题只需要 DFS 时记录累计和走到叶子节点判断一次即可。路径总和 II找到所有从根节点到叶子节点、路径和等于 targetSum 的路径并且要输出具体的路径节点序列。这需要 DFS 回溯维护一个路径列表。路径总和 III统计所有从上到下、任意起点到任意终点的路径数量路径和等于 targetSum。既不要求从根开始也不要求到叶子结束只统计数量不要求输出具体路径。第 III 题和前面两题最大的不同就是“任意起点”这个解放。如果还是用根到叶子的思路你会发现你漏掉了大量从中间节点开始的路径。比如一棵树的根节点是 10左子树是 5 → 3targetSum 8那么 5 → 3 这条路径是满足的但根节点根本不在这条路径上。如果你只从根出发做 DFS就会把这条路径漏掉。1.3 暴力解法的思路和局限第一次看到这道题大多数人的直觉是遍历每个节点把每个节点都当作起点往下 DFS 找路径和等于 targetSum 的路径数量。这就是所谓的“双重 DFS”外层遍历所有节点内层从当前节点出发往下搜索。伪代码如下int pathSum(TreeNode root, int targetSum) { if (root null) return 0; int count dfs(root, targetSum); // 以 root 为起点往下找 count pathSum(root.left, targetSum); // 递归处理左子树 count pathSum(root.right, targetSum); // 递归处理右子树 return count; } int dfs(TreeNode node, long curSum) { if (node null) return 0; int count 0; curSum - node.val; if (curSum 0) count; count dfs(node.left, curSum); count dfs(node.right, curSum); return count; }注意这里我用了一个小技巧把“路径和等于 targetSum”转化为“targetSum 减去路径上节点值之和等于 0”这样就不用额外维护累计和参数了。暴力解的时间复杂度是 O(n²)其中 n 是节点数。对于类似一条链的极端情况每个节点都要往下遍历剩余的所有节点复杂度会逼近 O(n²)。在 LeetCode 的测试数据下这个复杂度的代码通常也能通过因为二叉树的平均深度不高但如果你刷题只是“求过”你很容易被这种通过率误导。真正的面试官在追问“你的解法时间复杂度是多少”时如果你只能答出 O(n²)那这题的得分会打折扣。更重要的是暴力解里隐藏着一个很容易写错的地方外层递归和内层 DFS 的“职责”要分开。外层负责枚举起点内层负责从起点往下统计可行路径两者不能混。很多人在写的时候把“以当前节点为起点往下找”和“继续往子树递归”混在一个函数里导致路径数量算重复或者漏算。我自己刚开始刷这道题时就是这样写出来的代码跑测试用例能过一提交就差那么一两个用例。后来调试才发现是外层递归把当前节点往下的路径数重复计入了。所以如果要用暴力解建议把“寻找所有起点”和“从起点往下统计”拆成两个职责明确的函数别图省事合成一个。2. 前缀和优化——把树上的路径问题变成数组上的数学问题暴力解虽然能过但作为追求更优解的工程师肯定要往下想一步能不能在线性时间内解决能关键就在前缀和。2.1 前缀和在一维数组上的经典用法先回到一维数组的场景。给定一个整数数组 nums和一个目标值 k统计有多少个连续子数组的和等于 k。经典解法就是用前缀和加哈希表设 prefixSum[i] 表示 nums[0] 到 nums[i] 的前缀和那么子数组 nums[j1] 到 nums[i] 的和就等于 prefixSum[i] - prefixSum[j]。要找和为 k 的连续子数组就是找有多少对 i 和 j使得 prefixSum[i] - prefixSum[j] k等价于 prefixSum[j] prefixSum[i] - k。所以在遍历到第 i 个元素时只需要知道前面有多少个 prefixSum 等于 prefixSum[i] - k就能一次性统计出所有以 i 结尾的、和为 k 的子数组数量。用哈希表记录每种前缀和出现的次数查询是 O(1) 的整体时间复杂度降到了 O(n)。这个思想的核心是把“连续区间和等于 k”转化成“两个前缀和之差等于 k”用空间换时间。2.2 如何把前缀和“嫁接”到二叉树上二叉树和数组最大的区别在于数组是线性结构每个位置只有一个前驱二叉树是分支结构每个节点有左右两个后继。但如果你只看“从根到当前节点的路径”那么这条路径就是一个线性序列完全可以用前缀和来思考。定义从根节点到当前节点 p 的路径上所有节点值的和为 currSum。那么对于当前节点 p我们想知道的是在这条路径上有多少个节点 qq 在根和 p 之间包含根不包含 p使得从 q 到 p 的路径和等于 targetSum。从 q 到 p 的路径和 currSum - sumFromRootToParentOfQ。翻译成前缀和的语言就是我们要找在这条路径上是否存在某个前缀和 pre使得 currSum - pre targetSum也就是 pre currSum - targetSum。如果这条路径上某个前缀和 pre 出现了 cnt 次那么以当前节点 p 为终点、和为 targetSum 的路径就有 cnt 条。这个逻辑完全沿用了数组子数组求和的做法。但树和数组有一个非常大的区别数组的前缀和是“全局”的而树上的前缀和是“路径相关”的一条从根到左子树的路径和一条从根到右子树的路径它们各自的前缀和序列是独立的。你不能像数组那样从第一个元素一直扫到最后一个元素来维护一个单调的前缀和集合。这就引出了解决这道题最关键的操作回溯时恢复现场。当你从当前节点递归进入左子树时当前节点的前缀和应该保持在哈希表里递归进入右子树时也应该保持。但当左子树递归结束要回到当前节点、再进入右子树时你必须把刚才在左子树里新增的前缀和记录删掉否则右子树的路径统计会错误地使用到左子树的前缀和信息。这一点我在初学的时候想了好久才绕明白哈希表里如果残留了左子树某个节点的前缀和信息那么在当前节点的右子树里判断“某个前缀和出现了多少次”时会把左子树里那些不相干的路径也算进来导致结果偏大。2.3 状态管理的本质哈希表维护的到底是什么把哈希表 前缀和的方案理清楚核心就两个问题一、哈希表里存的 key 是什么是“从根到某个节点的路径上的节点值总和”也就是路径前缀和。二、哈希表里存的 value 是什么是“在当前递归路径上该前缀和出现了多少次”。注意“当前递归路径”这几个字它不是一个全局的概念而是随着 DFS 的推进不断变化的。为了更好理解可以用一个生活化的类比。假设你在一个迷宫里每经过一个路口你就在本子上记一笔“从入口到这里的累积里程”。当你站在某个位置时你想知道有没有一条从之前的某个路口到这里的路程刚好等于 targetSum你只需要拿当前累积里程减去 targetSum看看这个差值在之前的记录里出现过没有。这个本子就是哈希表。但是迷宫是分叉的。你从入口出发走了一条岔路到底折返回来再走另一条岔路。当你在第二条岔路里查看本子时你绝不应该把第一条岔路里的记录也算进来。这就要你在折返时把第一条岔路新记的内容擦掉。DFS 回溯时的 map.remove 操作干的就是这个“擦掉”的活儿。理解了这一点你就掌握了这类“在树/图上做前缀和计数”问题的全局视角。后面不管遇到二叉树、还是更复杂的图结构只要能在搜索路径上维护状态、在回溯时恢复基本都能套用这套思想。2.4 时间复杂度分析O(n) 是怎么来的用了前缀和 哈希表之后每个节点只被访问一次。每次访问时哈希表的查询和插入操作均摊复杂度都是 O(1)所以整体时间复杂度是 O(n)n 为树中节点数。空间复杂度方面递归栈深度决定了额外空间的上限。最坏情况下如果树是一条链递归深度是 n此时空间复杂度是 O(n)。平均情况下二叉树的深度是 O(logn)空间复杂度也就是 O(logn)。所以从复杂度角度前缀和方案和暴力方案是质的差别一个是线性扫描一个是近似平方级。面试的时候如果能从暴力解过渡到前缀和解法并且把复杂度分析讲清楚这题基本就稳了。3. 核心代码实现——三种语言对照逐行拆解关键细节光讲理论不动手是记不住的。这一节我会给出 Java、C、Python 三种语言的完整实现并对每个关键分支做注释。这三种语言的代码思路完全一样区别只是语法细节和类型处理。3.1 Java 实现用 Map 记录路径前缀和import java.util.HashMap; import java.util.Map; class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val val; this.left left; this.right right; } } class Solution { public int pathSum(TreeNode root, int targetSum) { // key前缀和value出现次数 MapLong, Integer prefixSumCount new HashMap(); // 初始化前缀和为 0 的路径有 1 条即不选任何节点 prefixSumCount.put(0L, 1); return dfs(root, 0L, targetSum, prefixSumCount); } private int dfs(TreeNode node, long currentSum, int targetSum, MapLong, Integer prefixSumCount) { if (node null) { return 0; } currentSum node.val; // 核心找出从某个祖先到当前节点路径和为 targetSum 的路径数量 long target currentSum - targetSum; int count prefixSumCount.getOrDefault(target, 0); // 将当前前缀和加入哈希表继续往下递归 prefixSumCount.put(currentSum, prefixSumCount.getOrDefault(currentSum, 0) 1); count dfs(node.left, currentSum, targetSum, prefixSumCount); count dfs(node.right, currentSum, targetSum, prefixSumCount); // 回溯恢复现场避免当前路径信息影响兄弟子树 prefixSumCount.put(currentSum, prefixSumCount.get(currentSum) - 1); if (prefixSumCount.get(currentSum) 0) { prefixSumCount.remove(currentSum); } return count; } }这里有个容易忽略的细节prefixSumCount.put(0L, 1)这一行。它表示“前缀和为 0 的路径存在 1 条”也就是从根节点出发的位置。为什么要初始化它因为如果从根节点到当前节点的累计和 currentSum 恰好等于 targetSum那么查找 currentSum - targetSum 0 时需要能查到 1 条记录这正是“从根节点出发的路径”被统计进去的关键。Java 语言里还有一个小坑树节点的 val 可能是负数targetSum 也可能是负数所以 currentSum 用long类型比较安全。当 targetSum 很大或节点值很极端时int 累加可能会溢出。虽然 LeetCode 的测试数据一般不触发这个边界但在实际工程里写代码尤其是处理累加和的场景用 long 是更稳妥的习惯。3.2 C 实现同样的思路更精简的表达#include unordered_map struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} }; class Solution { public: int pathSum(TreeNode* root, int targetSum) { unordered_maplong long, int prefixSumCount; prefixSumCount[0] 1; return dfs(root, 0LL, targetSum, prefixSumCount); } private: int dfs(TreeNode* node, long long currentSum, int targetSum, unordered_maplong long, int prefixSumCount) { if (node nullptr) { return 0; } currentSum node-val; long long target currentSum - targetSum; int count prefixSumCount.count(target) ? prefixSumCount[target] : 0; prefixSumCount[currentSum]; count dfs(node-left, currentSum, targetSum, prefixSumCount); count dfs(node-right, currentSum, targetSum, prefixSumCount); // 回溯恢复 prefixSumCount[currentSum]--; if (prefixSumCount[currentSum] 0) { prefixSumCount.erase(currentSum); } return count; } };C 版本和 Java 版本结构基本一致。有一个细节是prefixSumCount[currentSum]这一行会让不存在的 key 自动初始化为 0然后加 1。这看起来很简洁但需要注意 implicit 构造会引入默认值如果你在递归里频繁这样做哈希表的 size 可能会略微增大不过复杂度还是 O(n)问题不大。我个人的习惯是尽量少用这种隐式方式而是写成prefixSumCount[currentSum] prefixSumCount.count(currentSum) 0 ? 1 : prefixSumCount[currentSum] 1;虽然啰嗦一点但逻辑清楚面试时口述代码也不容易绕晕。3.3 Python 实现代码最短但要注意引用传递class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right class Solution: def pathSum(self, root: TreeNode, targetSum: int) - int: from collections import defaultdict prefixSumCount defaultdict(int) prefixSumCount[0] 1 def dfs(node: TreeNode, currentSum: int) - int: if not node: return 0 currentSum node.val target currentSum - targetSum count prefixSumCount.get(target, 0) prefixSumCount[currentSum] 1 count dfs(node.left, currentSum) count dfs(node.right, currentSum) # 回溯恢复 prefixSumCount[currentSum] - 1 if prefixSumCount[currentSum] 0: del prefixSumCount[currentSum] return count return dfs(root, 0)Python 的defaultdict在这里非常方便访问不存在的 key 会自动返回默认值。但要注意prefixSumCount[currentSum] - 1之后如果次数减到 0最好手动del掉这个 key。否则你可能会在后续路径上把“没出现过的前缀和”误认为出现了 0 次虽然结果一样查询时查到 0 和查不到都返回 0但哈希表的 size 会一直增长而且逻辑上不够干净。Python 递归里的 inner function 可以直接引用外部的 prefixSumCount 和 targetSum不需要像 Java、C 那样显式传参。但要注意 Python 默认递归深度限制是 1000如果题目的树的深度特别深比如一条 1000 层以上的链递归会爆栈。LeetCode 上这道题的测试数据一般不会触发这个限制但你在本地自己构造极端测试用例时得注意这一点。3.4 核心代码的五个关键细节分析完三种实现我强烈建议你把下面这五个细节刻在脑子里因为面试官常常在这五个点上追问第一初始化map[0] 1是干什么的回答为了让从根节点出发的合法路径能被统计到。如果一棵树根节点的 val 正好等于 targetSum当前 currentSum - targetSum 0此时需要查到这个 0 的记录存在路径数才能加 1。第二为什么在递归进入左右子树之前要把当前前缀和放入哈希表回答因为我们要统计的是“以当前节点为终点的路径”所以要保证从根到当前节点路径上的所有前缀和都记录在案这样后续的节点在以祖先为起点判断时才能正确查到对应的前缀和差值。第三为什么回溯时要删掉或减掉当前前缀和的次数回答因为二叉树的路径是分叉的我们不想让左子树的节点前缀和信息影响右子树的路径统计。这正是“路径独立性”的要求也是前缀和方案区别于数组方案的核心差异。第四currentSum为什么用 long 类型回答避免极端情况下 int 溢出。一个树深 1000 层、每层节点值都是 10^9 级别的链累计和会轻松超过 int 范围导致结果错误。第五为什么用getOrDefault而不是直接map.get回答因为哈希表里可能不存在目标前缀和直接get会返回 null在拆箱时触发空指针异常。无论是 Java 还是其他语言查询不存在的 key 都要做容错。4. 实操中的常见问题与排查经验——刷了几遍之后总结的避坑清单这道题在 LeetCode 里提交过多少次出现过多少种奇奇怪怪的错误恐怕比题目本身还精彩。我把我自己做题时遇到的、以及在评论区看到的典型问题做了个汇总分成几个类别来聊。4.1 “int 传递导致路径计数丢失”的问题很多初学者在写递归时会把 count 作为参数传递下去像这样int count 0; dfs(root, targetSum, count); // 错误示范然后发现 count 永远是 0。原因在于 Java 和 C 这类语言的函数参数传递基本类型是值传递你在子递归里对 count 的修改不会影响外层变量的值。所以要么用返回值累加要么把 count 放进一个数组或自定义对象里。上面给的三种语言实现全都采用返回值累加的方式这是最清晰、最不容易出错的做法。还有一种做法是把 count 作为类成员变量全局累加。这也能跑通但会导致递归函数之间共享状态如果这道题要在多组测试数据之间复用同一个 Solution 实例就很可能出现“上一次的结果残留”的 bug。我建议在面试时统一用返回值方案。4.2 “前缀和计数减到 0 但不删除 key”的隐患在我的经验里很多正确解法里只写prefixSumCount[currentSum]--但减到 0 后不删除 key。这在 LeetCode 上不会导致 WA因为查询时查到 0 和查不到都返回 0结果正确。但如果哈希表的 size 一直增大在极端构造下可能出现内存增长的问题而且逻辑上也不够清晰。更重要的是在某些变体题目里比如要求输出具体路径如果哈希表里残留了大量次数为 0 的 key会干扰后续对“是否存在这个前缀和”的判断。为避免后续可变性我的习惯是当次数减到 0 时直接删除 key。代价是一个if判断几乎可以忽略但换来的是哈希表始终保持只包含当前路径上真实存在的前缀和调试时看 map 的内容也一目了然。4.3 “漏掉负数导致前缀和查询出错”的认知误区有些人在做这道题时总觉得前缀和一定单调递增所以在查找差值时只往前找忽略了可能有负数的情况。但实际上这棵树的节点值可以是负数targetSum 也可以是负数所以前缀和序列并不是单调的。不过好消息是哈希表方案天然不依赖单调性。不管前缀和是增是减只要哈希表里的记录是准确的查询 currentSum - targetSum 永远是对的。这反而是前缀和方案比滑动窗口方案优势更大的地方。滑动窗口要求区间和单调不能处理负数而前缀和 哈希表完全不在乎值的正负。我在给初学的人讲这道题时一定会强调这一点哈希表方案之所以鲁棒是因为它把问题转化成了“两个前缀和的差值是否等于 target”而不是“边加边判断往哪边走”。后者在二叉树这种分支结构里根本不可行前者才是真正的线性做法。4.4 “空节点进入递归导致重复计数”的坑树的问题里空节点null处理是最容易写错的地方。常见的做法有两种第一种是在 dfs 开头判断if (node null) return 0。这样写很简单但要注意空节点不会产生任何路径计数也不会改变 currentSum返回 0 即可。第二种在调用 dfs 之前先判断子节点是否为空只在非空时才递归if (node.left ! null) { count dfs(node.left, currentSum, targetSum, prefixSumCount); }两种写法效果一样。我个人的习惯是统一在函数开头判断空节点这样可以少写几个if也不容易漏掉分支。但要注意如果采用了开头判断空节点的写法那对于空节点一定不要执行任何哈希表操作否则会把一个“虚拟的前缀和”记录进哈希表污染路径统计。4.5 调试技巧用小规模树验证中间状态如果代码跑出来结果不对我强烈建议别直接对着大测试数据瞎找原因而是构造一个小树手动模拟递归过程打印每一步的 currentSum 和哈希表内容。比如一个很经典的测试用例root [10, 5, -3, 3, 2, null, 11, 3, -2, null, 1], targetSum 8答案是 3。怎么算出来的三条路径分别是5 → 35 → 2 → 1-3 → 11。你可以在递归里加一个调试打印System.out.println(currentSum currentSum , target (currentSum - targetSum) , map prefixSumCount);这样就能观察到每个节点处哈希表到底存了什么也就能直观看到回溯删除 key 前后的变化。真正理解了 map 里的内容如何“随路径伸缩”这道题才算真会了。还有一个我常用的自测方法把暴力解和前缀和解同时跑一遍对随机生成的小规模二叉树节点数量 10 到 20 个值在 -5 到 5 随机对比两者的结果是否一致。如果一致大概率说明前缀和解法逻辑正确如果不一致就用小树 打印定位问题。这个方法我在刷很多二叉树题时都用效率非常高。4.6 常见错误速查表错误类型具体表现原因解决方案路径计数丢失结果始终为 0count 作为基本类型参数传递使用返回值累加或成员变量/引用类型结果偏大比预期多出几条路径遍历完左子树后没有回溯删除左子树的前缀和记录递归返回前将当前前缀和计数减 1减到 0 则删除空指针异常运行时报 NullPointer查询不存在的 key 时直接 intValue使用 getOrDefault或先判断 key 是否存在溢出大值测试下输出错误currentSum 使用 int 类型累加溢出使用 long 类型保存前缀和重复计数同一路径被统计多次外层遍历所有节点时内层 DFS 又重复包含起点节点自身明确区分“枚举起点”和“从起点出发统计”的职责结果偏小从根出发的路径未被统计没有初始化 map[0] 1在递归开始时手动插入 0 的计数这张表我建议收藏起来以后写任何“树 路径 前缀和”的题目时都能参考。你会发现很多类似的题目比如统计路径总和等于 target 的具体路径条数、最长路径和等本质上都是这几个坑的变体。5. 从 437 题看到的一类题目套路——前缀和在树上的扩展这道题做完如果不总结套路那是很大的浪费。437 题的价值不只在它本身更在于它展示了“前缀和”这种数据结构在树形结构上的一种应用范式。我用了不少时间把这类题目串起来看发现它们的共同点可以用一句话概括在一条根到节点的路径上寻找满足某种“区间差值条件”的节点对。5.1 变体题求和为 target 的最长路径长度有个很经典的变体题是二叉树中求所有路径中路径和等于 targetSum 的最长路径长度。路径的定义和 437 题一样可以任意起点、任意终点但要求向下。这道题可以用同样的前缀和思路但哈希表里存的就不只是“前缀和出现了几次”而是“前缀和最早出现在哪一层”。在遍历时对于当前节点如果 currentSum - targetSum 之前已经出现过那么路径长度就是当前层数减去历史层数。为了求最长路径记录最早出现的层数即可。这道题的代码几乎和 437 题同构唯一的区别就是 map 的 value 从 count 变成了 depth以及递归返回时需要把 map 恢复到进入节点之前的状态。学了 437 题再去写这个变体基本相当于换汤不换药。5.2 变体题路径总和 II 的输出形式扩展另一类变体是要求输出具体的路径节点序列不只是数量。这时前缀和哈希表方案就不够用了因为你虽然能快速知道存在多少条路径却无法直接回溯出路径上的具体节点。这类题通常是暴力 DFS 回溯时维护 path 列表或者用哈希表存的 value 更复杂一些。但从底层思维来说都是“路径状态 回溯”。这也是为什么我一直建议刷题时不要死记代码模板而要掌握“路径上维护状态信息、回溯时恢复状态”这个元方法。437 题就是最好的题源因为它把这种方法压缩在一段不到 30 行的代码里。5.3 从一道题迁移到一类题总结属于自己的模板我自己的习惯是每做完一道有代表性的题就把它的框架抽取成模板。以 437 题为例我能抽象出的模板是初始化哈希表记录基础状态 定义递归函数(node, 当前状态, 目标条件): if node 为空: 返回默认值 更新当前状态 根据 当前状态 和目标条件从哈希表里查询需要的信息累加到结果 将当前状态写入哈希表 递归处理子树汇总结果 回溯将当前状态从哈希表移除/恢复 返回结果这个模板适用于三类题目统计路径满足某种条件的数量437 题求路径满足某种条件的极值长度最长路径和等于 target判断是否存在满足条件的路径路径总和 I / II 的变体把模板用熟了你在面试中看到“二叉树 路径 和/差/最长/数量”这些字眼时就不会一头雾水而是能快速判断“这是不是要我维护路径前缀和然后在递归过程中查询差值”5.4 刷题之外的工程意义可能有人说这题在工程上能用到哪其实真有用。树形结构在前端组件树、文件目录树、组织架构树里都很常见。比如一个常见的需求给定一个目录树统计所有子目录的大小之和等于某个值的路径数量或者是组织架构里统计某个职级以下的团队人力总和满足条件的汇报链。虽然业务系统里不会真有 targetSum 这种直白的概念但“在树路径上做区间聚合统计”这件事情底层用的也是同样的遍历和状态管理思路。更重要的是前缀和思想本身维护累计值 哈希表查询历史在流式数据处理、数组区间查询、股票收益计算等场景都非常常见。437 题只是把这个思想放到了树上。所以刷这一道题学到的不只是一个题解而是一种可以迁移到多个领域的建模能力。6. 复盘与思考——我消化 437 题的方式最后这部分就不列代码了聊点我个人的“消化过程”。这题我前后刷了可能得有五六遍每一遍感觉都不一样。第一遍是照着暴力解代码抄过了第二遍是看前缀和解法能读懂但自己写还是漏回溯第三遍能独立写出来但被面试官一追问复杂度就卡壳到后面几遍才开始真正理解“为什么要在递归返回前恢复哈希表”这个动作而不是机械地记忆代码。如果你现在正处于“照着题解能写自己写就卡”的阶段我的建议是不要急着背解法而是把每一行代码都问一个为什么。为什么map.put(0, 1)因为根节点路径需要被统计。为什么在递归子树之前把当前前缀和放进去因为后续节点要把它当作可能的起点。为什么递归返回时要恢复现场因为每条根到叶子路径是独立的。把这几个问题想通了你会发现这类题后面的逻辑是顺下来的根本不需要死记硬背。哪怕有一天你忘了具体代码只要还记得“前缀和 哈希表 回溯恢复现场”这个组合你就能在面试现场把代码重新推导出来。另外437 题在 Hot 100 里的热门程度本身也说明了它的价值。Hot 100 的题目筛选是有讲究的它既要覆盖高频面试考点也要涵盖不同难度梯度和思想类型。437 题之所以入选大概率就是因为它用最朴素的二叉树场景考察了“前缀和 递归 回溯”这几个算法基础元素是一个相当综合的训练场。如果你正在刷 Hot 100我个人的刷题顺序建议是把二叉树相关的题目放到一起刷比如 104、112、113、437 这几道放一起先做简单的求深度、判定路径和再做输出路径最后做任意起点终点计数。这样由浅入深你对“路径”这个概念的理解会比单刷任何一道题都要深刻得多。我把这题放在个人博客里当成一个“树 路径问题的代表题”来复盘每次重读自己写过的分析都还能发现新的细节。这也是我为什么推荐你在刷题之余用自己的话把题解思路写一遍。写作是很好的思维整理工具当你发现自己能在不对照代码的情况下把“为什么”讲清楚时这题才算真正属于你了。最后再分享一个小技巧如果面试时时间紧张先把暴力解的思路说清楚再提出可以用前缀和优化。这么做有两个好处一是向面试官展示你具备从低效到高效的优化意识二是就算最后代码没写完你已经展示了自己的思路层级面试官通常也会给一个不错的评价。写代码之前先把话说清楚往往比闷头写代码更让面试官放心。