优化)
最近在过力扣热题100的二叉树专题路径总和 III 这道题LeetCode 437可以说是整张列表里最能拉开差距的一道题。它表面就是个简单的路径求和实际却考察了两个层次能不能写出一个正确但慢的解法以及能不能想到用前缀和把复杂度从 O(N²) 降到 O(N)。这两层恰好对应了面试里工程实现能力和算法思路深度的区分。这篇文章就从我自己的刷题过程出发把双重递归和前缀和哈希表两种解法讲透然后把讨论区里常见的疑问、我踩过的坑一并说清楚。适合正在刷力扣热题100的人也适合想彻底搞懂前缀和套路的人。1. 题目拆解路径总和 III 到底在考什么1.1 我第一次读题时的理解偏差我第一次看到这道题时脑子里第一个反映是这不就是标准的根节点到叶子节点的路径求和吗DFS 一路加下去到底了就判断和是否等于 targetSum然后把值返回上来。这样的题目在热题100里有一道原型的路径总和 I那个确实只需要判断根到叶子有没有一条路径。但路径总和 III 的题目描述里有一句话彻底改变了问题性质路径不需要从根节点开始也不需要在叶子节点结束。这就意味着路径的起点可以是树里的任意节点终点也可以是任意后代节点整条路径只要保证方向是向下的就行。换句话说我们在遍历的时候不能像以前一样只维护一条从根到当前节点的候选路径而是要考虑一个子树里所有可能的连续向下片段。这个变化导致暴力的思考方式完全不一样起点要枚举终点也要跟着往下走。1.2 路径方向的限制只能向下不能回头只能向下这四个字很多人扫一眼就过去了实际操作时才发现这是个很强的约束。因为有这个限制一条合法的路径一定落在从某个祖先节点到某个后代节点的这条直线上它不会拐弯不会在某个节点分成两叉再合并。比如 root 到左子树某个节点是一条链root 到右子树某个节点是另一条链这两条链不可能拼成一条路径。这个限制的另一个含义是如果我们在递归里处理当前节点那么所有以它为终点的路径其实都已经由它祖先们的前缀信息决定了。而所有以它为起点的路径又需要向后代去延伸。这个起点和终点的视角直接决定了后面双重递归和前缀和两种解法的组织方式。我一开始没想清楚这一点导致写双重递归的时候函数职责混乱一会儿在 pathSum 里累加一会儿在 dfs 里累加最后统计结果重复了不少。1.3 容易被忽略的负数节点值题目里节点值的范围是 -10^9 到 10^9targetSum 的范围也包含负数。这意味着一个很常见的前缀优化思路——当前和已经大于 targetSum 就提前返回——在本题是行不通的。我见过不少人在这里写了一个if (sum targetSum) return 0;然后自信满满地提交结果用例一片红。原因很简单路径上可能出现负数当前和超了 targetSum往后加一个负数又把它拉回来了。比如路径是 5 - -3 - 4targetSum 为 6走到 5 (-3) 2 时小于目标走到 5 (-3) 4 6 正好命中。如果只做正数和这根本不会发生但本题的边界条件明确包含了负数所以任何剪枝都必须基于当前路径和加上后续所有可能的和都不够这种数学上严格成立的判断而不是简单地和 targetSum 比大小。这道题被标记为中等难度很大程度上就是因为这个负数边界让很多贪心剪枝失效逼着你往枚举所有路径或者前缀和的方向走。2. 双重递归解法先跑通一个正确版本2.1 设计思路以每个节点为路径起点最朴素但一定正确的思路是把问题拆成两层第一层遍历整棵树的每一个节点把每个节点都当作一条路径的起点。第二层从这个起点出发沿向下方向继续递归沿途累加节点值一旦累加和等于 targetSum计数加一并且继续往下走而不是停下来因为后面可能有负数拉回也可能出现另一个恰好等于 targetSum 的终点。为什么第一层要遍历每个节点因为路径可以从树里任何一个节点开始。为什么第二层找到等于 targetSum 后还要继续因为路径不需要在叶子节点结束而节点值可以为负同一个起点可能对应多个不同的终点都满足条件。比如一条路径上累计和先到 5过了一个 -2 又到 5如果 targetSum 是 5这个起点就贡献了两条路径。2.2 递归函数拆解pathSum 和 dfs 的分工我用 Python 实现的第一版是这样class Solution: def pathSum(self, root: TreeNode, targetSum: int) - int: if not root: return 0 # 第一层把每个节点都当作起点 ans self.dfs(root, targetSum) # 从当前节点出发 ans self.pathSum(root.left, targetSum) # 左子树里找起点 ans self.pathSum(root.right, targetSum) # 右子树里找起点 return ans def dfs(self, node: TreeNode, targetSum: int) - int: # 第二层从 node 出发沿向下方向累加 if not node: return 0 cnt 0 if node.val targetSum: cnt 1 cnt self.dfs(node.left, targetSum - node.val) cnt self.dfs(node.right, targetSum - node.val) return cnt注意 pathSum 和 dfs 的参数含义不一样pathSum 里的root表示我在这棵子树里寻找合法路径dfs 里的node表示路径必须从当前节点开始。这层区分特别重要。如果混在一起很容易出现对同一个路径重复统计的问题。我在第一版就犯过这个错把ans self.pathSum(root.left, targetSum)写成了ans self.dfs(root.left, targetSum)导致只统计了从 root 的左孩子为起点的路径漏掉了左孩子子树里更深层起点的路径。2.3 双重递归的时间复杂度与面试定位这个解法的时间复杂度怎么算外层 pathSum 会访问每个节点一次内层 dfs 又会从每个起点出发向下走一遍。最坏情况是树退化成一条链深度为 N每个起点向下走 O(N)整体就是 O(N²)。比较理想的情况下比如平衡二叉树每个节点向下走的深度是 O(log N)整体是 O(N log N)。空间复杂度基本是递归栈深度 O(N)最坏退化成链表时也是 O(N)。在面试里这个解法虽然慢但它是很好的baseline。你先把一个一定能跑对的版本写出来一方面验证自己理解题意没有偏差另一方面给了自己一个对照基准后面写优化版本的时候可以拿它来对拍验证。很多刷题的人一上来就想写最优解结果边界条件处理错了还不知道反而是先写暴力再优化的节奏更稳。我在实际面试模拟中也发现面试官普遍不会因为你先给出 O(N²) 解法就否定你他更看重你能不能在此基础上继续优化以及为什么能想到用前缀和来替代内层循环。3. 前缀和 哈希表从 O(N²) 到 O(N) 的关键优化3.1 什么是前缀和为什么能匹配路径前缀和这个概念在很多题目里都出现过数组、子数组求和那类题尤其常见。它的核心是把从某一段起点到终点的连续和转化为两个从开头算起的累计和的差值。放到二叉树里如果我们沿着根节点一路向下累加每个节点都会有一个从根节点到当前节点的路径和这就是树上的前缀和。假设我们从根节点到某个祖先节点 A 的路径和是 S1继续向下走到后代节点 B 的路径和是 S2那么 A 到 B 这一段路径的和就是 S2 - S1。这就是前缀和能匹配路径的本质原因。它把枚举起点终点这个 O(N²) 的操作变成了维护一个前缀和集合判断当前前缀和减去目标值是否在集合中出现过。3.2 核心公式推导用两个前缀和的差值表示路径和我们设prefix(node)表示从根节点到当前节点的路径和。对于一条从祖先 A 到后代 B 的路径它的路径和可以写成pathSum(A - B) prefix(B) - prefix(parent(A))这里的parent(A)是指在 A 的父节点处结束的前缀这样减掉之后恰好剩下 A 到 B 这一段。如果我们希望 pathSum(A - B) targetSum那就有prefix(B) - prefix(parent(A)) targetSum prefix(parent(A)) prefix(B) - targetSum所以在 DFS 到当前节点 B 的时候只要检查从根到某个节点的路径和是不是等于 prefix(B) - targetSum就能知道有多少条以 B 为终点、从任意祖先节点开始的路径满足条件。这个过程我们不需要真的去遍历那些祖先只需要维护一个哈希表记录已经出现的各种前缀和次数。有一个很容易绕晕的地方为什么公式里要写parent(A)而不是 A 本身因为 A 到 B 的路径包含 A 节点的值。如果写成prefix(B) - prefix(A)那就是把 A 的值剪掉了。要保留 A 节点的值必须拿 B 的前缀和减去 A 父节点的前缀和。这个细节我在纸上推了几遍才彻底想清楚写代码时也容易错位成cur_sum - target去哈希表里找但哈希表里存的该是祖先节点前缀和两者恰好是同一个值所以代码里看起来就是hash[cur_sum - target]。3.3 哈希表的作用与更新顺序哈希表里存的是某个前缀和值出现过的次数。这里有个关键顺序在递归到当前节点时必须先查哈希表再把自己加入哈希表顺序反了会统计错误。为什么因为我们找的是祖先节点的前缀和当前节点自己是不能作为自己的祖先的。如果先把当前节点的前缀和加进哈希表再去查cur_sum - target那么当 targetSum 0 时查出来的次数里会多包含自己一次路径长度是 0这显然不合法。所以严谨的顺序一定是计算当前累计和 cur_sum。查询哈希表中cur_sum - targetSum出现的次数累加到答案。把当前节点的cur_sum计数加一。递归处理左右子树。回溯时把当前节点的cur_sum计数减一。这个顺序如果写反遇到 targetSum 0 的用例时你会莫名多出几条路径而且还不容易发现必须靠对拍才能定位。3.4 回溯时的删除操作为什么必不可少这是整个讨论区里问得最多的问题。假设我不做回溯删除直接把所有遍历过的前缀和都留在哈希表里会发生什么比如我先遍历完了左子树哈希表里存着左子树上很多前缀和然后去遍历右子树。右子树的某个节点去查询cur_sum - target时可能匹配到左子树上某个祖先前缀和。但右子树和左子树并不在一条自上而下的路径上用左子树的前缀和减出来的路径和根本不存在。所以回溯删除的本质是哈希表里只保留当前路径上的祖先节点前缀和路径一转向就要把不属于这条路径的前缀和移除。这是一个很经典的DFS 回溯配合全局状态的模式很多使用前缀和的树上题目都依赖这一点。我第一次没有删除直接提交结果测试用例挂了一片后来逐步排查才意识到是这个原因。4. 完整实现与代码逐行注释4.1 Python 版本力扣刷题的主流语言实现既然是力扣热题100Python 解法自然是重点毕竟很多人就是用 Python 刷题的。我最终通过的最优解版本如下class Solution: def pathSum(self, root: TreeNode, targetSum: int) - int: # 前缀和哈希表初始必须放入前缀和为 0 的情况 prefix {0: 1} self.ans 0 self.target targetSum def dfs(node: TreeNode, cur_sum: int) - None: if not node: return # 累加当前节点值得到从根到当前节点的前缀和 cur_sum node.val # 查询 cur_sum - target 出现的次数 # 这个次数就是以当前节点为终点时满足条件的路径数 self.ans prefix.get(cur_sum - self.target, 0) # 将当前前缀和存入哈希表供子节点查询使用 prefix[cur_sum] prefix.get(cur_sum, 0) 1 # 递归处理左右子树 dfs(node.left, cur_sum) dfs(node.right, cur_sum) # 回溯当前节点处理完毕把它的前缀和计数减掉 prefix[cur_sum] - 1 # 如果计数减到 0也可以直接删除这个 key if prefix[cur_sum] 0: del prefix[cur_sum] dfs(root, 0) return self.ans这段代码最需要注意的就是prefix {0: 1}这条初始化。它表示从根节点开始路径和为 0 的路径存在一次。为什么要这样初始化因为当cur_sum - target 0时意味着从根节点到当前节点的整条路径和恰好等于 targetSum这是一种合法的路径它的起点是根节点的父节点。但根节点没有父节点我们需要用这个初始的计数 1 来代表这个空路径前缀。缺失这行初始化的话所有从根节点开始的合法路径都会被漏掉。4.2 代码走读每一行在做什么我用一个具体的小树走一遍感受一下整个过程。假设树是最简单的三个节点10 / \ 5 -3targetSum 为 15。合法的路径只有 10 5 这一条10 加 -3 等于 7不符合单独的 10 也不符合。从 root 节点 10 开始cur_sum 变成 10查询10 - 15 -5哈希表里没有ans 不变然后插入prefix[10] 1递归左子树。进入节点 5cur_sum 变成 10 5 15查询15 - 15 0哈希表里有prefix[0] 1于是 ans 加一这就是根节点路径 10 5 被统计了一次。接着插入prefix[15] 1节点 5 的左右子树为空返回前执行回溯prefix[15]减一变成 0删除 key。回到节点 10继续走右子树节点 -3cur_sum 变成 10 - 3 7查询7 - 15 -8哈希表里没有ans 不变。整个过程结束后 ans 等于 1结果正确。注意节点 5 处理完后删除了prefix[15]如果这里不删后续右子树走到其它节点时只要某个节点的cur_sum - target 15就会误算一条不存在的路径这就是上一节说的左子树污染右子树问题。4.3 测试用例覆盖正数、负数和零我自己刷题习惯在本地把边界用例先跑一遍而不是直接提交。针对这道题我长期维护了几个固定用例用例树结构targetSum期望结果验证重点空树None任意0根节点为空的边界单节点[1]11从根到自身的路径单节点[1]00不能算空路径全正链1-2-3-461单向链上的前缀和含负数[1,-2,-3] 等-12负数路径判断target为0[1,-1]011 (-1) 这条路径完全相同值[1,1,1]2211 出现两条子路径比如[1, -2, -3]它其实是一个三节点的二叉树1 是根-2 和 -3 是左右孩子。targetSum 为 -1 时根到左孩子路径和是 -1左孩子自身也是 -1所以期望结果是 2。这个用例专门用来验证找到一条后不能停还要继续往下走因为左孩子自身就满足条件但它没有孩子所以也要能统计到。如果代码里写成找到一次就 return这里就会漏掉一条。5. 刷题过程中踩过的坑和排查链路5.1 坑一哈希表初始值到底该放什么这是我第一次写前缀和解法时第一个挂的地方。我没有初始化prefix[0] 1直接给它一个空字典然后所有从根节点出发且恰好等于 targetSum的路径全部漏掉。一开始我还以为是公式写错了反复检查cur_sum - target的运算方向后来用最简单的[1]、targetSum 为 1 的用例调试才发现cur_sum - target 0但哈希表根本没有 key 0所以查询结果永远是 0。排查的逻辑其实很清楚如果整棵树的根节点到当前节点的路径本身就是一个合法答案那它对应的是cur_sum - target 0这个 0 代表的是根节点之前的空前缀。任何情况下你都需要把空前缀的计数初始化成 1这是在动态规划类和前缀和类题目里非常通用的一个技巧。遇到类似题目第一件事就是想想起点之前是什么。5.2 坑二先加还是先查顺序不同结果不同这个坑在 targetSum 为 0 的用例下立刻暴露。我第一次写的时候把prefix[cur_sum] prefix.get(cur_sum, 0) 1放在了查询之前结果目标是 0 时cur_sum - target cur_sum查出来的次数包含了当前节点自身等于给答案多加了一条长度为 0 的路径。单节点 [5] 且 targetSum 为 0 的情况下正确结果是 0我的代码却输出 1。排查的时候我一度怀疑是递归结构的问题后来打日志发现哈希表更新时机不对。正确的做法很简单永远先查询再把自己写进表里。这样查出来的所有前缀和都来自严格意义上的祖先节点不可能出现自己匹配自己的情况。如果你把这套逻辑在心里默念一遍——当前节点的答案取决于祖先们的前缀和而不包含自己——顺序就不会再搞错。5.3 坑三递归进入左子树前为什么要把当前前缀和删掉说实话这个坑不是一次定位的而是长期混淆。很多人包括我最初遇到错误输出的第一反应是是不是我忘了把prefix传进递归是不是闭包作用域有问题其实都不是问题恰恰是记得太牢忘记删了。我可以描述一下我的完整排查链路。某次我在一个三层二叉树上测试targetSum 为 5树是根 1、左子树 2、右子树 100左子树 2 下面还有一个左子树 2。正确路径有两条122 和单独的一个 2 组成的路径注意这里需要其它分支配合。但我的代码输出了多条额外路径。我在dfs第一步打印所有哈希表内容发现遍历右子树时哈希表里还残留着左子树上某个节点前缀和为 3 的记录而右子树的某个节点恰好也有cur_sum - target 3于是被误匹配了。修复方案一共两行代码但理解它需要建立DFS 栈的直觉递归进入某条分支前当前路径上的节点会把它们的前缀和依次写入哈希表从这条分支返回后这些节点已经不属于后续路径的祖先集合必须从哈希表里撤销。撤销的方式是把计数减一减到 0 就删除 key。如果减到 0 后不删除而是让 key 保留为 0 也没关系因为查不到 0 次加不到答案里但为了内存干净我在代码里选择了删除。5.4 坑四找到一条等于 targetSum 的路径后要不要继续这个坑在双重递归版本里特别明显。有的实现里写着if node.val target: count; return count;看上去很有道理找到了就返回嘛路径已经结束了。问题是路径不需要在叶子节点结束所以即使当前节点值等于剩余目标也还可以继续往下走。比如一条路径上走了 5、-2、2targetSum 是 5那么前缀为 5 时命中一次走完 5、-2、2 后总和还是 5又可以命中一次。如果你在第一次命中时返回第二层其实漏掉了一半答案。加了一个负数测试用例之后这个问题立刻暴露。以后凡是遇到路径不需要在叶子节点结束的题目我都会提醒自己命中目标只是记录不是终止信号。前缀和解法天然没有这个坑因为它是查哈希表不是逐点比较但双重递归版本很容易让人顺手加个 return。6. 面试官视角这道题背后的考点与延伸6.1 从路径总和 III 看前缀和题型的共性刷了力扣热题100之后你会发现前缀和不是一个孤立技巧它是一个大的题型家族。最常见的是数组场景里的和为 K 的子数组LeetCode 560那道题的核心思想与此完全一致遍历数组时维护前缀和哈希表找cur_sum - k出现的次数。唯一的区别是数组天然是一条单向线性结构不需要回溯删除而树的分支结构让它多了一份状态撤销的负担。还有二维矩阵里的和为 K 的子矩阵LeetCode 1074思想是把矩阵压缩成多个数组再跑前缀和。如果把树和数组放在一起对比你会看到同一个公式prefix[j] - prefix[i] target在不同数据结构上的变体。这其实是一种极为核心的思维模型当你需要频繁计算任意子段的和且总和查询是瓶颈时前缀和几乎总是首选。理解了这一点笔试里遇到类似题目你就会自动往这个方向想而不是靠背模板。6.2 面试中的追问方向如果不限制只能向下呢面试官如果看到你熟练写出了前缀和解法通常会进一步追问如果路径不限制方向可以从任意节点出发经过边到达任意其他节点但每条边只能走一次你会怎么做这种变体本质上已经变成了树的直径的加权重构对每个节点考虑通过该节点连接左右两条向下的路径拼接成一条绕过该节点的完整路径。此时前缀和的思路就不能直接用了因为你需要在每个节点处合并左右子树各自的最优路径。我建议在有时间的情况下把这两个变体都实现一遍因为它们的思路切换非常考验对路径这个概念的理解。一个是严格的祖先-后代链一个是任意两点间的简单路径所用的 DFS 返回值的语义完全不同前者返回计数后者返回以该节点为端点的最大单侧路径和。真正理解了这两者的区别你遇到任何树上的路径题都能迅速判断它在考什么。6.3 我个人刷这道题的实际体会这道题我前前后后写了大概四版才到最优解。第一版是错误理解题意只做了根到叶子的路径判断第二版是双重递归跑通了但超时第三版前缀和但忘了初始化prefix[0] 1结果一路漏答案第四版才算完整。整个过程最大的教训是不要急着优化先确认自己真的理解路径可以从任意节点开始、到任意节点结束这句话。另外我建议刷完这道题后顺手把和为 K 的子数组也做一遍两边对照着看你会发现树的前缀和其实就是数组前缀和加了一个回溯而已。这个认知一旦建立以后再遇到二叉树里的最大路径和LeetCode 124这类题你对递归返回值和全局变量怎么分工的把握也会上一个台阶。LeetCode 热题100 里的题目之所以经典不是因为难而是因为每道题背后都拖着一串可以横向扩展的知识点路径总和 III 就是这串知识点非常典型的入口。
路径总和III：从双重递归到前缀和哈希表的O(N)优化
最近在过力扣热题100的二叉树专题路径总和 III 这道题LeetCode 437可以说是整张列表里最能拉开差距的一道题。它表面就是个简单的路径求和实际却考察了两个层次能不能写出一个正确但慢的解法以及能不能想到用前缀和把复杂度从 O(N²) 降到 O(N)。这两层恰好对应了面试里工程实现能力和算法思路深度的区分。这篇文章就从我自己的刷题过程出发把双重递归和前缀和哈希表两种解法讲透然后把讨论区里常见的疑问、我踩过的坑一并说清楚。适合正在刷力扣热题100的人也适合想彻底搞懂前缀和套路的人。1. 题目拆解路径总和 III 到底在考什么1.1 我第一次读题时的理解偏差我第一次看到这道题时脑子里第一个反映是这不就是标准的根节点到叶子节点的路径求和吗DFS 一路加下去到底了就判断和是否等于 targetSum然后把值返回上来。这样的题目在热题100里有一道原型的路径总和 I那个确实只需要判断根到叶子有没有一条路径。但路径总和 III 的题目描述里有一句话彻底改变了问题性质路径不需要从根节点开始也不需要在叶子节点结束。这就意味着路径的起点可以是树里的任意节点终点也可以是任意后代节点整条路径只要保证方向是向下的就行。换句话说我们在遍历的时候不能像以前一样只维护一条从根到当前节点的候选路径而是要考虑一个子树里所有可能的连续向下片段。这个变化导致暴力的思考方式完全不一样起点要枚举终点也要跟着往下走。1.2 路径方向的限制只能向下不能回头只能向下这四个字很多人扫一眼就过去了实际操作时才发现这是个很强的约束。因为有这个限制一条合法的路径一定落在从某个祖先节点到某个后代节点的这条直线上它不会拐弯不会在某个节点分成两叉再合并。比如 root 到左子树某个节点是一条链root 到右子树某个节点是另一条链这两条链不可能拼成一条路径。这个限制的另一个含义是如果我们在递归里处理当前节点那么所有以它为终点的路径其实都已经由它祖先们的前缀信息决定了。而所有以它为起点的路径又需要向后代去延伸。这个起点和终点的视角直接决定了后面双重递归和前缀和两种解法的组织方式。我一开始没想清楚这一点导致写双重递归的时候函数职责混乱一会儿在 pathSum 里累加一会儿在 dfs 里累加最后统计结果重复了不少。1.3 容易被忽略的负数节点值题目里节点值的范围是 -10^9 到 10^9targetSum 的范围也包含负数。这意味着一个很常见的前缀优化思路——当前和已经大于 targetSum 就提前返回——在本题是行不通的。我见过不少人在这里写了一个if (sum targetSum) return 0;然后自信满满地提交结果用例一片红。原因很简单路径上可能出现负数当前和超了 targetSum往后加一个负数又把它拉回来了。比如路径是 5 - -3 - 4targetSum 为 6走到 5 (-3) 2 时小于目标走到 5 (-3) 4 6 正好命中。如果只做正数和这根本不会发生但本题的边界条件明确包含了负数所以任何剪枝都必须基于当前路径和加上后续所有可能的和都不够这种数学上严格成立的判断而不是简单地和 targetSum 比大小。这道题被标记为中等难度很大程度上就是因为这个负数边界让很多贪心剪枝失效逼着你往枚举所有路径或者前缀和的方向走。2. 双重递归解法先跑通一个正确版本2.1 设计思路以每个节点为路径起点最朴素但一定正确的思路是把问题拆成两层第一层遍历整棵树的每一个节点把每个节点都当作一条路径的起点。第二层从这个起点出发沿向下方向继续递归沿途累加节点值一旦累加和等于 targetSum计数加一并且继续往下走而不是停下来因为后面可能有负数拉回也可能出现另一个恰好等于 targetSum 的终点。为什么第一层要遍历每个节点因为路径可以从树里任何一个节点开始。为什么第二层找到等于 targetSum 后还要继续因为路径不需要在叶子节点结束而节点值可以为负同一个起点可能对应多个不同的终点都满足条件。比如一条路径上累计和先到 5过了一个 -2 又到 5如果 targetSum 是 5这个起点就贡献了两条路径。2.2 递归函数拆解pathSum 和 dfs 的分工我用 Python 实现的第一版是这样class Solution: def pathSum(self, root: TreeNode, targetSum: int) - int: if not root: return 0 # 第一层把每个节点都当作起点 ans self.dfs(root, targetSum) # 从当前节点出发 ans self.pathSum(root.left, targetSum) # 左子树里找起点 ans self.pathSum(root.right, targetSum) # 右子树里找起点 return ans def dfs(self, node: TreeNode, targetSum: int) - int: # 第二层从 node 出发沿向下方向累加 if not node: return 0 cnt 0 if node.val targetSum: cnt 1 cnt self.dfs(node.left, targetSum - node.val) cnt self.dfs(node.right, targetSum - node.val) return cnt注意 pathSum 和 dfs 的参数含义不一样pathSum 里的root表示我在这棵子树里寻找合法路径dfs 里的node表示路径必须从当前节点开始。这层区分特别重要。如果混在一起很容易出现对同一个路径重复统计的问题。我在第一版就犯过这个错把ans self.pathSum(root.left, targetSum)写成了ans self.dfs(root.left, targetSum)导致只统计了从 root 的左孩子为起点的路径漏掉了左孩子子树里更深层起点的路径。2.3 双重递归的时间复杂度与面试定位这个解法的时间复杂度怎么算外层 pathSum 会访问每个节点一次内层 dfs 又会从每个起点出发向下走一遍。最坏情况是树退化成一条链深度为 N每个起点向下走 O(N)整体就是 O(N²)。比较理想的情况下比如平衡二叉树每个节点向下走的深度是 O(log N)整体是 O(N log N)。空间复杂度基本是递归栈深度 O(N)最坏退化成链表时也是 O(N)。在面试里这个解法虽然慢但它是很好的baseline。你先把一个一定能跑对的版本写出来一方面验证自己理解题意没有偏差另一方面给了自己一个对照基准后面写优化版本的时候可以拿它来对拍验证。很多刷题的人一上来就想写最优解结果边界条件处理错了还不知道反而是先写暴力再优化的节奏更稳。我在实际面试模拟中也发现面试官普遍不会因为你先给出 O(N²) 解法就否定你他更看重你能不能在此基础上继续优化以及为什么能想到用前缀和来替代内层循环。3. 前缀和 哈希表从 O(N²) 到 O(N) 的关键优化3.1 什么是前缀和为什么能匹配路径前缀和这个概念在很多题目里都出现过数组、子数组求和那类题尤其常见。它的核心是把从某一段起点到终点的连续和转化为两个从开头算起的累计和的差值。放到二叉树里如果我们沿着根节点一路向下累加每个节点都会有一个从根节点到当前节点的路径和这就是树上的前缀和。假设我们从根节点到某个祖先节点 A 的路径和是 S1继续向下走到后代节点 B 的路径和是 S2那么 A 到 B 这一段路径的和就是 S2 - S1。这就是前缀和能匹配路径的本质原因。它把枚举起点终点这个 O(N²) 的操作变成了维护一个前缀和集合判断当前前缀和减去目标值是否在集合中出现过。3.2 核心公式推导用两个前缀和的差值表示路径和我们设prefix(node)表示从根节点到当前节点的路径和。对于一条从祖先 A 到后代 B 的路径它的路径和可以写成pathSum(A - B) prefix(B) - prefix(parent(A))这里的parent(A)是指在 A 的父节点处结束的前缀这样减掉之后恰好剩下 A 到 B 这一段。如果我们希望 pathSum(A - B) targetSum那就有prefix(B) - prefix(parent(A)) targetSum prefix(parent(A)) prefix(B) - targetSum所以在 DFS 到当前节点 B 的时候只要检查从根到某个节点的路径和是不是等于 prefix(B) - targetSum就能知道有多少条以 B 为终点、从任意祖先节点开始的路径满足条件。这个过程我们不需要真的去遍历那些祖先只需要维护一个哈希表记录已经出现的各种前缀和次数。有一个很容易绕晕的地方为什么公式里要写parent(A)而不是 A 本身因为 A 到 B 的路径包含 A 节点的值。如果写成prefix(B) - prefix(A)那就是把 A 的值剪掉了。要保留 A 节点的值必须拿 B 的前缀和减去 A 父节点的前缀和。这个细节我在纸上推了几遍才彻底想清楚写代码时也容易错位成cur_sum - target去哈希表里找但哈希表里存的该是祖先节点前缀和两者恰好是同一个值所以代码里看起来就是hash[cur_sum - target]。3.3 哈希表的作用与更新顺序哈希表里存的是某个前缀和值出现过的次数。这里有个关键顺序在递归到当前节点时必须先查哈希表再把自己加入哈希表顺序反了会统计错误。为什么因为我们找的是祖先节点的前缀和当前节点自己是不能作为自己的祖先的。如果先把当前节点的前缀和加进哈希表再去查cur_sum - target那么当 targetSum 0 时查出来的次数里会多包含自己一次路径长度是 0这显然不合法。所以严谨的顺序一定是计算当前累计和 cur_sum。查询哈希表中cur_sum - targetSum出现的次数累加到答案。把当前节点的cur_sum计数加一。递归处理左右子树。回溯时把当前节点的cur_sum计数减一。这个顺序如果写反遇到 targetSum 0 的用例时你会莫名多出几条路径而且还不容易发现必须靠对拍才能定位。3.4 回溯时的删除操作为什么必不可少这是整个讨论区里问得最多的问题。假设我不做回溯删除直接把所有遍历过的前缀和都留在哈希表里会发生什么比如我先遍历完了左子树哈希表里存着左子树上很多前缀和然后去遍历右子树。右子树的某个节点去查询cur_sum - target时可能匹配到左子树上某个祖先前缀和。但右子树和左子树并不在一条自上而下的路径上用左子树的前缀和减出来的路径和根本不存在。所以回溯删除的本质是哈希表里只保留当前路径上的祖先节点前缀和路径一转向就要把不属于这条路径的前缀和移除。这是一个很经典的DFS 回溯配合全局状态的模式很多使用前缀和的树上题目都依赖这一点。我第一次没有删除直接提交结果测试用例挂了一片后来逐步排查才意识到是这个原因。4. 完整实现与代码逐行注释4.1 Python 版本力扣刷题的主流语言实现既然是力扣热题100Python 解法自然是重点毕竟很多人就是用 Python 刷题的。我最终通过的最优解版本如下class Solution: def pathSum(self, root: TreeNode, targetSum: int) - int: # 前缀和哈希表初始必须放入前缀和为 0 的情况 prefix {0: 1} self.ans 0 self.target targetSum def dfs(node: TreeNode, cur_sum: int) - None: if not node: return # 累加当前节点值得到从根到当前节点的前缀和 cur_sum node.val # 查询 cur_sum - target 出现的次数 # 这个次数就是以当前节点为终点时满足条件的路径数 self.ans prefix.get(cur_sum - self.target, 0) # 将当前前缀和存入哈希表供子节点查询使用 prefix[cur_sum] prefix.get(cur_sum, 0) 1 # 递归处理左右子树 dfs(node.left, cur_sum) dfs(node.right, cur_sum) # 回溯当前节点处理完毕把它的前缀和计数减掉 prefix[cur_sum] - 1 # 如果计数减到 0也可以直接删除这个 key if prefix[cur_sum] 0: del prefix[cur_sum] dfs(root, 0) return self.ans这段代码最需要注意的就是prefix {0: 1}这条初始化。它表示从根节点开始路径和为 0 的路径存在一次。为什么要这样初始化因为当cur_sum - target 0时意味着从根节点到当前节点的整条路径和恰好等于 targetSum这是一种合法的路径它的起点是根节点的父节点。但根节点没有父节点我们需要用这个初始的计数 1 来代表这个空路径前缀。缺失这行初始化的话所有从根节点开始的合法路径都会被漏掉。4.2 代码走读每一行在做什么我用一个具体的小树走一遍感受一下整个过程。假设树是最简单的三个节点10 / \ 5 -3targetSum 为 15。合法的路径只有 10 5 这一条10 加 -3 等于 7不符合单独的 10 也不符合。从 root 节点 10 开始cur_sum 变成 10查询10 - 15 -5哈希表里没有ans 不变然后插入prefix[10] 1递归左子树。进入节点 5cur_sum 变成 10 5 15查询15 - 15 0哈希表里有prefix[0] 1于是 ans 加一这就是根节点路径 10 5 被统计了一次。接着插入prefix[15] 1节点 5 的左右子树为空返回前执行回溯prefix[15]减一变成 0删除 key。回到节点 10继续走右子树节点 -3cur_sum 变成 10 - 3 7查询7 - 15 -8哈希表里没有ans 不变。整个过程结束后 ans 等于 1结果正确。注意节点 5 处理完后删除了prefix[15]如果这里不删后续右子树走到其它节点时只要某个节点的cur_sum - target 15就会误算一条不存在的路径这就是上一节说的左子树污染右子树问题。4.3 测试用例覆盖正数、负数和零我自己刷题习惯在本地把边界用例先跑一遍而不是直接提交。针对这道题我长期维护了几个固定用例用例树结构targetSum期望结果验证重点空树None任意0根节点为空的边界单节点[1]11从根到自身的路径单节点[1]00不能算空路径全正链1-2-3-461单向链上的前缀和含负数[1,-2,-3] 等-12负数路径判断target为0[1,-1]011 (-1) 这条路径完全相同值[1,1,1]2211 出现两条子路径比如[1, -2, -3]它其实是一个三节点的二叉树1 是根-2 和 -3 是左右孩子。targetSum 为 -1 时根到左孩子路径和是 -1左孩子自身也是 -1所以期望结果是 2。这个用例专门用来验证找到一条后不能停还要继续往下走因为左孩子自身就满足条件但它没有孩子所以也要能统计到。如果代码里写成找到一次就 return这里就会漏掉一条。5. 刷题过程中踩过的坑和排查链路5.1 坑一哈希表初始值到底该放什么这是我第一次写前缀和解法时第一个挂的地方。我没有初始化prefix[0] 1直接给它一个空字典然后所有从根节点出发且恰好等于 targetSum的路径全部漏掉。一开始我还以为是公式写错了反复检查cur_sum - target的运算方向后来用最简单的[1]、targetSum 为 1 的用例调试才发现cur_sum - target 0但哈希表根本没有 key 0所以查询结果永远是 0。排查的逻辑其实很清楚如果整棵树的根节点到当前节点的路径本身就是一个合法答案那它对应的是cur_sum - target 0这个 0 代表的是根节点之前的空前缀。任何情况下你都需要把空前缀的计数初始化成 1这是在动态规划类和前缀和类题目里非常通用的一个技巧。遇到类似题目第一件事就是想想起点之前是什么。5.2 坑二先加还是先查顺序不同结果不同这个坑在 targetSum 为 0 的用例下立刻暴露。我第一次写的时候把prefix[cur_sum] prefix.get(cur_sum, 0) 1放在了查询之前结果目标是 0 时cur_sum - target cur_sum查出来的次数包含了当前节点自身等于给答案多加了一条长度为 0 的路径。单节点 [5] 且 targetSum 为 0 的情况下正确结果是 0我的代码却输出 1。排查的时候我一度怀疑是递归结构的问题后来打日志发现哈希表更新时机不对。正确的做法很简单永远先查询再把自己写进表里。这样查出来的所有前缀和都来自严格意义上的祖先节点不可能出现自己匹配自己的情况。如果你把这套逻辑在心里默念一遍——当前节点的答案取决于祖先们的前缀和而不包含自己——顺序就不会再搞错。5.3 坑三递归进入左子树前为什么要把当前前缀和删掉说实话这个坑不是一次定位的而是长期混淆。很多人包括我最初遇到错误输出的第一反应是是不是我忘了把prefix传进递归是不是闭包作用域有问题其实都不是问题恰恰是记得太牢忘记删了。我可以描述一下我的完整排查链路。某次我在一个三层二叉树上测试targetSum 为 5树是根 1、左子树 2、右子树 100左子树 2 下面还有一个左子树 2。正确路径有两条122 和单独的一个 2 组成的路径注意这里需要其它分支配合。但我的代码输出了多条额外路径。我在dfs第一步打印所有哈希表内容发现遍历右子树时哈希表里还残留着左子树上某个节点前缀和为 3 的记录而右子树的某个节点恰好也有cur_sum - target 3于是被误匹配了。修复方案一共两行代码但理解它需要建立DFS 栈的直觉递归进入某条分支前当前路径上的节点会把它们的前缀和依次写入哈希表从这条分支返回后这些节点已经不属于后续路径的祖先集合必须从哈希表里撤销。撤销的方式是把计数减一减到 0 就删除 key。如果减到 0 后不删除而是让 key 保留为 0 也没关系因为查不到 0 次加不到答案里但为了内存干净我在代码里选择了删除。5.4 坑四找到一条等于 targetSum 的路径后要不要继续这个坑在双重递归版本里特别明显。有的实现里写着if node.val target: count; return count;看上去很有道理找到了就返回嘛路径已经结束了。问题是路径不需要在叶子节点结束所以即使当前节点值等于剩余目标也还可以继续往下走。比如一条路径上走了 5、-2、2targetSum 是 5那么前缀为 5 时命中一次走完 5、-2、2 后总和还是 5又可以命中一次。如果你在第一次命中时返回第二层其实漏掉了一半答案。加了一个负数测试用例之后这个问题立刻暴露。以后凡是遇到路径不需要在叶子节点结束的题目我都会提醒自己命中目标只是记录不是终止信号。前缀和解法天然没有这个坑因为它是查哈希表不是逐点比较但双重递归版本很容易让人顺手加个 return。6. 面试官视角这道题背后的考点与延伸6.1 从路径总和 III 看前缀和题型的共性刷了力扣热题100之后你会发现前缀和不是一个孤立技巧它是一个大的题型家族。最常见的是数组场景里的和为 K 的子数组LeetCode 560那道题的核心思想与此完全一致遍历数组时维护前缀和哈希表找cur_sum - k出现的次数。唯一的区别是数组天然是一条单向线性结构不需要回溯删除而树的分支结构让它多了一份状态撤销的负担。还有二维矩阵里的和为 K 的子矩阵LeetCode 1074思想是把矩阵压缩成多个数组再跑前缀和。如果把树和数组放在一起对比你会看到同一个公式prefix[j] - prefix[i] target在不同数据结构上的变体。这其实是一种极为核心的思维模型当你需要频繁计算任意子段的和且总和查询是瓶颈时前缀和几乎总是首选。理解了这一点笔试里遇到类似题目你就会自动往这个方向想而不是靠背模板。6.2 面试中的追问方向如果不限制只能向下呢面试官如果看到你熟练写出了前缀和解法通常会进一步追问如果路径不限制方向可以从任意节点出发经过边到达任意其他节点但每条边只能走一次你会怎么做这种变体本质上已经变成了树的直径的加权重构对每个节点考虑通过该节点连接左右两条向下的路径拼接成一条绕过该节点的完整路径。此时前缀和的思路就不能直接用了因为你需要在每个节点处合并左右子树各自的最优路径。我建议在有时间的情况下把这两个变体都实现一遍因为它们的思路切换非常考验对路径这个概念的理解。一个是严格的祖先-后代链一个是任意两点间的简单路径所用的 DFS 返回值的语义完全不同前者返回计数后者返回以该节点为端点的最大单侧路径和。真正理解了这两者的区别你遇到任何树上的路径题都能迅速判断它在考什么。6.3 我个人刷这道题的实际体会这道题我前前后后写了大概四版才到最优解。第一版是错误理解题意只做了根到叶子的路径判断第二版是双重递归跑通了但超时第三版前缀和但忘了初始化prefix[0] 1结果一路漏答案第四版才算完整。整个过程最大的教训是不要急着优化先确认自己真的理解路径可以从任意节点开始、到任意节点结束这句话。另外我建议刷完这道题后顺手把和为 K 的子数组也做一遍两边对照着看你会发现树的前缀和其实就是数组前缀和加了一个回溯而已。这个认知一旦建立以后再遇到二叉树里的最大路径和LeetCode 124这类题你对递归返回值和全局变量怎么分工的把握也会上一个台阶。LeetCode 热题100 里的题目之所以经典不是因为难而是因为每道题背后都拖着一串可以横向扩展的知识点路径总和 III 就是这串知识点非常典型的入口。
