路径总和III：从暴力DFS到前缀和+哈希表的最优解

刷到热题100的第437题时我一开始的想法很简单这不就是在二叉树上数路径吗结果动手一写才发现这题和之前做过的“路径总和”、“路径总和II”完全不是一回事。路径总和判断的是“根节点到叶子节点”是否存在一条满足条件的路路径总和II还要你把路径打印出来而437题的路径起点和终点都是任意的只要沿着父节点到子节点的方向往下走任何一段连续路径都算数。这种“任意起点、任意终点”的小改动直接把难度拉高了一档。这篇文章我打算从最直观的暴力解法开始讲一步步过渡到面试官真正想听的前缀和哈希表解法再把实现细节、边界条件和容易踩的坑全部过一遍。无论你是刚开始刷二叉树的新手还是已经能把递归写得行云流水的老手这篇文章应该都能给你一点新的思考角度。1. 别被“路径总和”这个名字骗了三道题的演进决定了这题的难度1.1 从“根到叶子”到“任意向下路径”题意发生了质变力扣里“路径总和”系列一共有三道题我建议你按顺序刷因为它们的难度是递进的题目起点终点要求路径总和根节点叶子节点判断是否存在路径总和II根节点叶子节点返回所有满足条件的路径路径总和III任意节点任意后代节点统计满足条件的路径数量前两道的路径被限定得很死必须从根出发必须到叶子为止。所以它们的解法就是标准的先序遍历走到叶子节点时判断累加和是否等于目标值。这里有个关键细节由于题目没限制节点值和目标值的正负实际上很多用例里含有负数你不能在累加和等于目标值时提前返回必须走完整个分支才能确定答案。而437题的“任意起点”意味着什么意味着树上的每一个节点都有资格成为某条合法路径的起点。这样一来原先那种“从根一路走到叶子”的单次遍历就不够了——你需要枚举所有起点对每个起点再向下枚举所有终点。这才是437题真正的难点所在。1.2 “任意起点”让暴力解法的时间复杂度直接翻倍我画个极端例子你就明白了。如果一棵树是链状结构比如每个节点只有右孩子那么这棵树退化成一条长度为n的链表。此时从第1个节点出发有n-1个可选终点从第2个节点出发有n-2个可选终点……总路径数量是12...n也就是O(n^2)量级。即便是一棵平衡二叉树起点数有n个每个起点向下延伸的平均深度也只有O(log n)左右总工作量是O(n log n)。这就是暴力和优化的分水岭暴力解法我们当然要会写它能帮助你验证思路、跑通测试用例但面试时如果只给出暴力解法面试官基本上会接着问一句“能不能优化到O(n)”。所以接下来的思路是先写出暴力再理解为什么暴力慢最后搞清楚前缀和是怎么把复杂度降下来的。2. 暴力解法双重DFS先把“能过”的方案写出来2.1 核心思路外层枚举起点内层向下累加暴力解法的思路非常直接分成两层递归外层递归负责枚举路径的起点。以当前节点为起点时调用一个内部函数从这个起点出发向下累加。内层递归负责在固定起点的情况下向下扩展路径每走到一个节点就判断“从起点到当前节点的路径和”是否等于目标值。如果等于计数加1。这里有一个容易和前面几题混淆的点内层递归中即使累加和已经等于目标值了也不能停止向下遍历。比如目标值是5一条路径是5 - 0 - 0累加和第一次到达5时如果直接返回就会漏掉后面两个同样是5的终点。又比如10 - -5在10这个节点累加和还没到5但加上后面的-5后刚好等于5。所以内层遍历必须走到叶子节点为止。写成Java代码就是下面这样class Solution { public int pathSum(TreeNode root, int targetSum) { if (root null) { return 0; } // 以当前节点为起点搜一遍 在左子树里继续枚举起点 在右子树里继续枚举起点 return rootSum(root, targetSum) pathSum(root.left, targetSum) pathSum(root.right, targetSum); } private int rootSum(TreeNode node, long targetSum) { if (node null) { return 0; } int count 0; if (node.val targetSum) { count; } // 注意这里不能用 node.val targetSum 就返回 count rootSum(node.left, targetSum - node.val); count rootSum(node.right, targetSum - node.val); return count; } }Python版本也顺手贴出来逻辑完全一致class Solution: def pathSum(self, root: Optional[TreeNode], targetSum: int) - int: if root is None: return 0 return self.root_sum(root, targetSum) \ self.pathSum(root.left, targetSum) \ self.pathSum(root.right, targetSum) def root_sum(self, node: Optional[TreeNode], target_sum: int) - int: if node is None: return 0 count 1 if node.val target_sum else 0 count self.root_sum(node.left, target_sum - node.val) count self.root_sum(node.right, target_sum - node.val) return count2.2 为什么内层递归用 targetSum - node.val 这种写法很多同学第一次写内层递归时会习惯性地维护一个curSum每走到一个节点就curSum node.val然后判断curSum targetSum。这种写法没问题但有一种更简洁的等价写法不要累加当前和而是把目标值不断减去节点值。如果某个节点值等于剩余目标值说明从起点到这里的路径和正好等于原始目标值。用targetSum - node.val的好处是省去了一个“当前累计和”变量代码更干净也更容易看出递归的数学含义每往下走一步需要凑的差值就减少相应节点值。不过如果为了和后面前缀和解法保持一致你也可以在内部维护一个curSum没有本质区别。2.3 暴力的复杂度以及为什么OJ能过但面试可能会被追问暴力解法在最坏情况下时间复杂度是O(n^2)其中n是节点总数。空间复杂度是O(n)主要消耗在递归调用栈上——当树退化成链时递归深度最大可以达到n。在热题100的测试数据里暴力解法其实是可以提交通过的毕竟题目限定的数据规模不算特别夸张。但如果你在面试中写出了这个版本最好主动把复杂度分析说清楚然后告诉面试官这个解法能过是因为数据范围允许但理论上还可以优化到O(n)用前缀和哈希表来做。展现出这种“我会暴力但我知道怎么优化”的状态往往比只会背最优解更能加分。3. 前缀和登场把树上任意向下路径变成两个前缀和的差3.1 先回顾一维数组的最经典做法和为K的子数组要理解437的最优解绕不开一道更简单的题给一个整数数组和一个目标值K统计有多少个连续子数组的和等于K。这题的暴力做法是枚举所有子数组O(n^2)。但有一个经典优化定义前缀和pre[i]表示数组前i个元素的和。那么从第i1个元素到第j个元素的连续子数组和等于pre[j] - pre[i]。要找和为K的子数组就是找满足pre[j] - pre[i] K的(i, j)对也就是pre[i] pre[j] - K。具体实现时用一个哈希表记录“当前已经出现过哪些前缀和、各出现多少次”。从头扫描数组每次遇到pre[j]就去哈希表里查pre[j] - K出现了多少次这个次数就是以j结尾、且和为K的连续子数组个数。3.2 把树的路径对齐成前缀和之差树结构的路径本质上也是一个“连续区间”——只不过区间是从某个祖先节点延伸到某个后代节点。如果我们维护一个变量curSum表示从根节点到当前遍历到的节点的路径和那么树上任意一条向下路径的和都可以用两个这样的前缀和相减得到。假设路径的起点是节点p终点是当前节点node那么路径和等于curSum(node) - curSum(parent(p))。其中parent(p)表示p的父节点。如果p本身就是根节点那么parent(p)为空相当于前缀和为0的空路径。也就是说要判断从某个祖先p到当前节点node的路径和是否等于targetSum只需要检查curSum(parent(p))是否等于curSum(node) - targetSum。这听起来有点绕但本质和一维数组完全一样。数组里是“前i个元素和”与“前j个元素和”之差树里是“根到某个祖先的父节点”与“根到当前节点”的前缀和之差。两者的关键都落在想办法快速查出所有满足条件的前缀和。3.3 为什么树上需要“回溯”而数组不需要数组是线性结构从左到右扫过去每个前缀和全局共用所有历史前缀和都可以保留。但树是分叉结构在左子树里积累的前缀和记录不能带进右子树。例如根节点有两个子节点进入右子树时如果哈希表里还留着左子树某个节点的前缀和那么在查询右子树里的路径时可能会错误匹配到左子树的节点计算出根本不存在的路径。所以树上应用前缀和套路时必须在递归返回的时候撤销状态。这就是“回溯”出现在这里的根本原因。你不需要背诵“这道题要回溯”只要想清楚“左右子树的前缀和记录必须互相隔离”自然就会在递归结束后删除自己添加的记录。一旦理解了这一点代码基本不会写错。4. 回溯哈希表的完整实现正确性、代码与三个必踩的坑4.1 先查再更新然后遍历子树最后回溯前缀和哈希表的实现核心就一句话每到一个节点先查“以当前节点为终点的合法路径有多少条”再把当前节点的前缀和记录进哈希表遍历完左右子树后删除该记录。完整Java代码如下class Solution { private MapLong, Integer prefixMap new HashMap(); private long targetSum; public int pathSum(TreeNode root, int targetSum) { this.targetSum targetSum; // 这个0非常关键代表“空节点”的前缀和 prefixMap.put(0L, 1); return dfs(root, 0L); } private int dfs(TreeNode node, long curSum) { if (node null) { return 0; } curSum node.val; // 先查以当前节点为终点起点上方的前缀和需要等于 curSum - targetSum int count prefixMap.getOrDefault(curSum - targetSum, 0); // 再更新把当前前缀和记录下来 prefixMap.put(curSum, prefixMap.getOrDefault(curSum, 0) 1); count dfs(node.left, curSum); count dfs(node.right, curSum); // 回溯撤销当前节点对后续兄弟子树的影响 prefixMap.put(curSum, prefixMap.get(curSum) - 1); return count; } }Python版本from collections import defaultdict class Solution: def pathSum(self, root: Optional[TreeNode], targetSum: int) - int: prefix defaultdict(int) prefix[0] 1 self.target_sum targetSum self.ans 0 def dfs(node: Optional[TreeNode], cur_sum: int) - None: if node is None: return cur_sum node.val self.ans prefix[cur_sum - self.target_sum] prefix[cur_sum] 1 dfs(node.left, cur_sum) dfs(node.right, cur_sum) prefix[cur_sum] - 1 dfs(root, 0) return self.ans代码量很少但正确性推理值得展开说说假设当前节点是nodecurSum是根到node的路径和。任何一条以node为终点的合法路径都对应着一个起点p使得curSum(node) - curSum(parent(p)) targetSum也就是curSum(parent(p)) curSum(node) - targetSum。到达node时哈希表里存储的是“根到node这条路径上所有节点包括根节点的虚拟父节点的前缀和出现次数”所以prefixMap[curSum - targetSum]的值就是所有以node为终点、且路径和等于targetSum的路径数量。因为每条路径只有一个终点按终点分类统计每个路径恰好被计入一次不会重复也不会遗漏。4.2 三个必踩的坑第一个坑是最经典的哈希表里漏了put(0L, 1)。这个初始键值代表“根节点之前的空路径前缀和”。如果没有它所有从根节点出发的合法路径都会被漏掉。举个例子一棵树只有一个根节点值等于targetSum没有0 - 1这个初始记录查询时prefixMap[curSum - targetSum]查到的是prefixMap[0]结果是0正确答案1就没了。新手很容易在这里翻车。第二个坑是更新顺序。必须先查再更新不能先更新再查。如果targetSum恰好等于0先更新的话当前节点的前缀和curSum被记录下来紧接着查询prefixMap[curSum - 0]就会把自己刚加入的记录也算进去导致多计一条“从当前节点到当前节点且和为0”的路径。这看起来像是正确的单个节点路径和确实可以是0但前提是节点值本身为0而不是用curSum去凑实际上会造成系统性错误。第三个坑是忘记回溯。很多同学写递归时记得进入子树前更新状态却忘了递归返回后恢复状态。这导致左子树的前缀和记录污染右子树的查询结果。我自己的习惯是写完递归调用之后立刻检查一遍看有没有需要“撤销”的操作宁可先写一个prefixMap.put(curSum, prefixMap.get(curSum) - 1)也不要在出问题时再回来补。4.3 为什么用long而不是int题目里单节点值范围看似安全但路径和是沿途所有节点值的累加。当树高较大、节点值全是负数或全是正数时累加和很容易超出int范围在做减法时还可能带来溢出异常。所以无论是暴力版本还是前缀和版本建议直接把前缀和类型声明为long。这在面试中也是一个能体现经验的细节。5. 边界用例与复杂度从“能过”到“所有情况都对”5.1 这些测试用例一定要自己过一遍写完之后先别急着提交手推几个边界场景空树root为null路径数量为0。前缀和解法里dfs(root, 0)直接返回0。单节点树节点值为targetSum答案是1否则是0。targetSum为0的树这最容易出错。如果每个节点的值不为0但路径上正负值相消也能凑出很多路径。此时前缀和里keycurSum和curSum - 0相等尤其要注意查询顺序。全负数节点同样能构成合法路径。暴力解法中不能因为当前累加和已经小于目标值就剪枝负数会继续拉低累加和。我自己常用的验证方式是构造一个结构简单的树用暴力法和前缀和法同时跑比对结果。比如下面这棵树targetSum11 / \ 2 -3 / \ 3 1手数答案路径1根节点本身1条路径2 - 1第二条路径累加和3不对路径1右子树叶子节点本身1条路径-3 - 1根到右子树叶子累加和-2不对路径1 - 2 - 3累加和6不对路径2 - 35不对路径1左子树右叶子1条。正确答案是2。这个用例能帮你同时检查暴力递归和前缀和逻辑。5.2 复杂度细节对比前缀和解法每个节点只会被访问一次每次访问只做常数次哈希表操作时间复杂度是O(n)。空间复杂度主要由递归栈深度和哈希表大小决定最坏情况下树退化成链递归深度O(n)哈希表存了n个不同前缀和总共O(n)。平衡树情况下递归深度O(log n)哈希表长度还是O(n)总体依然是O(n)空间。对比一下暴力解法解法时间复杂度空间复杂度适用性双重DFS最坏O(n^2)平衡树O(n log n)O(n)数据规模小思路直白前缀和哈希表O(n)O(n)标准最优解面试推荐可以看出前缀和解法不仅在时间上有优势代码结构也足够清晰面试时优先写这一版更稳妥。5.3 从“过用例”到“过边界”的检查顺序我平时提交前会按这个顺序自我检查先检查空树再检查根节点单节点然后构造一条链状树验证递归深度不会爆栈最后构造一个含有正负数且目标值为0的树验证查询顺序和回溯逻辑。特别是目标值为0的情况用三个节点值为1, -1, 1的链状树手算一遍能迅速暴露“先更新后查询”的错误。6. 举一反三前缀和哈希表还能解决哪些同类题6.1 回顾经典变式一维连续子数组求和前缀和哈希表最原始的形态就是“和为K的连续子数组数量”。把树的路径问题理解成一维问题的“树上版本”之后你会发现两道题的配对数表几乎一模一样唯一区别就是树遍历需要回溯数组遍历不需要。如果拿这两道题一起刷收获会非常大。刷题时遇到“连续子数组”、“连续子序列”、“向下路径”这类字眼先想想能不能用前缀和套路。6.2 如果题目改成“打印所有满足条件的路径”怎么办有些公司面试会在437基础上加一个要求不仅要统计数量还要把所有路径打印出来。这时候前缀和哈希表就有点力不从心了因为哈希表只存次数不存具体位置。一个可行方案退回到DFS维护一条“从根到当前节点”的路径列表每进入一个节点从当前路径的末尾向前遍历枚举所有以当前节点为终点的子路径满足条件就记录。由于要输出路径本身复杂度至少是O(n^2)量级因为输出数量本身可能就有这么多这和统计数量问题有本质区别。在面试中遇到这种扩展一定要先说清楚“如果需要输出具体路径复杂度无法避免地会变高”。6.3 二维矩阵前缀和也是同一套思想再往外延伸一点二维矩阵中求子矩阵和为target的问题也可以用二维前缀和预处理再对每一行区间枚举列边界配合哈希表降到O(m * n^2)或更好。这个思路和一维情形一脉相承只是细节更多。真正理解“前缀和之差 区间和”这个等式后从数组到树再到矩阵都是同一套底层逻辑。6.4 我建议的练习顺序不要一上来就背最优解。先按“暴力DFS - 发现复杂度问题 - 推前缀和思路 - 手写前缀和代码 - 验证边界”的顺序走一遍。这个过程走下来你会对递归、回溯、状态管理有很具体的体感而不是停留在背模板。等遇到其他变形题时至少知道往哪个方向想。我个人在写这类题时还有一个习惯在纸上把树画出来把每个节点的“根到该节点的前缀和”标在旁边。标完之后你会发现任意两个节点之间的路径和就是它们前缀和之差整棵树的信息一下就清晰了。437这道题之所以能成为热题100里的常客就是因为它把“前缀和、哈希表、回溯、递归”四个高频考点全揉在了一起一道题吃透相当于同时复习了二叉树和数组两类经典套路。