尧图网站开发 
LeetCode 124这道题全称 Binary Tree Maximum Path Sum中文一般叫二叉树中的最大路径和在二叉树递归题里属于绕不开的经典。我第一次刷到它的时候被一个路径绕了很久因为题目允许路径从任意节点出发、到任意节点结束而且可以拐弯跟平时习惯的根到叶子完全不是一回事。这篇文章我把完整的思路、代码、踩坑都写出来想彻底吃透这道题的朋友可以一步步照着推。这道题解决的核心问题是给定一棵二叉树每个节点有权值可能是负数找到一条任意走向的路径让路径上所有节点的值加起来最大。它适合正在刷二叉树递归的人、准备算法面试的人还有想系统整理树形 DP 思路的人。看完之后你会发现这类题的代码其实很短难点全在状态定义上。1. 先从题目本身说起1.1 题面到底在问什么先翻译一遍题面给你一棵非空二叉树每个节点上有一个整数值可能为正也可能为负。你要找出一条路径使得路径经过的所有节点值之和最大返回这个最大值。这里有几个关键限定需要抠清楚路径可以从任意节点开始到任意节点结束不需要经过根节点。路径中每个节点只能经过一次不能走回头路。路径至少包含一个节点不能是空路径。一个节点只有左右两个子节点所以路径在某个节点处最多只能拐一次弯。很多人第一次看到任意节点到任意节点会懵心里想这到底怎么枚举二叉树里任意两个节点之间不是有唯一路径吗难道要枚举所有点对如果真去枚举点对复杂度就是O(n²)显然不是题目想考的。实际上这道题考的是如何在一次树形遍历中同时维护向下延伸的单链和可以拐弯的完整路径两类信息。把题目理解成在一棵树上找一条连续路径让路径权值和最大就对了。树的路径跟数组子数组最大的区别是数组是线性的路径不能跳树是分叉的路径在某个节点处可以选择从左子树来、到右子树去形成一次拐弯。1.2 为什么这道题是必刷经典刷题圈子里经常说二叉树递归有三座大山最大路径和、直径、最近公共祖先。124题能成为经典我觉得有三个原因。第一递归状态设计得非常典型。它要求你分清楚给父节点返回什么和自己局部能更新出什么答案这个区分在树形 DP 里反复出现。弄懂这一题后面做打家劫舍 III、监控二叉树、最长同值路径之类的题会顺很多。第二它对路径这个概念的理解要求很高。如果只知道路径是连续走的一段很容易写出只往一个方向走的错误代码。必须意识到路径可以在某个节点上拐弯而拐弯点恰恰就是路径上深度最小的那个节点。第三面试高频且衍生性强。很多公司会把这道题当基础题考然后立刻加限制比如如果节点值都是正数怎么做如果要求路径必须经过根节点怎么做如果改成求最长路径长度直径怎么做。2. 核心思路从后序遍历到状态定义2.1 先想清楚一件事路径为什么能拐弯在一棵二叉树里任意两个节点之间的路径是唯一的因为树中没有环。这条唯一路径可以看作向上走到某个公共祖先再向下走到目标节点。举个例子一棵树长这样1 / \ 2 3 / \ \ 4 5 6节点4到节点6的路径是4 - 2 - 1 - 3 - 6。这条路径在节点1处拐了一个弯左侧部分是4 - 2右侧部分是3 - 6中间夹着节点1。所以完整路径可以拆成三段从左子树向下延伸的一条链 拐弯节点本身 从右子树向下延伸的一条链。两侧的链可以退化为空也就是说路径可以只往一个方向走甚至只有一个节点。这个拆法非常关键因为它把任意两点路径变成了每个节点当拐弯中心的问题。我们只需要遍历每个节点算出以它为拐弯中心能组成的最大路径然后取全局最大值即可。2.2 递归状态怎么定义既然要以每个节点为拐弯中心那递归函数就需要知道从当前节点往下走能走出的最大单链值是多少。注意这里刻意强调单链因为只有单链才能作为完整路径的半边交给父节点拼接。我习惯把这个函数叫做dfs(node)含义是从 node 出发沿着子节点向下走到任意位置形成的单条链的最大节点值之和。所谓单条链就是路径只能一直往一个方向走不能分叉。比如从节点1出发可以走1 - 2可以走1 - 3 - 6但这些都是一条直线。那么dfs(node)怎么算它等于node.val max(dfs(node.left), dfs(node.right))等等这里需要处理一个细节如果某个子树返回的值是负数带上它只会让总和变小。比如dfs(node.left) -5那我还不如不选左子树让左半边为空。所以更严谨的写法是node.val max(0, dfs(node.left), dfs(node.right))也就是每个子树的贡献先和0取最大值负贡献直接丢弃。这个贡献和0取max的操作是整道题的核心思想之一。2.3 局部答案怎么更新现在有了单链值下一步就是在每个节点处计算经过该节点、可能拐弯的完整路径的最大值。刚才说过完整路径 左链 节点 右链。左链和右链都可以为空所以当前节点作为拐弯中心时最大完整路径为max(0, dfs(node.left)) node.val max(0, dfs(node.right))这个值只对当前节点有意义它不能再往上传递因为往上传递时路径只能作为一条单链不能两边都带着。如果父节点还要用你这边的结果它只能收到一条链不能收到一个V字形。所以整棵树的答案就是在所有节点的完整路径候选值里取最大值。用一个全局变量ans来记录每遍历到一个节点就更新一次。这里就是树形 DP 最常见的套路每个递归函数返回局部最优但可拼接的信息同时用一个外部变量收集全局最优但不可拼接的信息。前者给上层用后者作为最终答案。3. 代码实现与逐行解读3.1 最精简的 Java 代码先把代码贴出来然后逐行拆。class Solution { private int ans Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { dfs(root); return ans; } private int dfs(TreeNode node) { if (node null) { return 0; } int leftGain Math.max(0, dfs(node.left)); int rightGain Math.max(0, dfs(node.right)); int currentPathSum leftGain node.val rightGain; ans Math.max(ans, currentPathSum); return node.val Math.max(leftGain, rightGain); } }整个代码只有十几行但每一行都有讲究。root为空的情况题目不会给但递归过程中子节点会为空所以dfs的终止条件必须处理null返回 0 表示空子树对父节点没有任何贡献。leftGain和rightGain分别表示左右子树能给当前节点的最大单链贡献小于 0 就当 0 处理。这一点特别重要它隐含了一个决策如果某边是负收益我就不走那边让路径半边为空。currentPathSum是以当前节点为拐弯中心的完整路径和。注意这里用的是leftGain node.val rightGain不是node.val Math.max(leftGain, rightGain)。前者允许拐弯后者只是单链。ans维护所有拐弯中心里最大的那个就是最终答案。return node.val Math.max(leftGain, rightGain)是给父节点使用的单链值只能从左右两边选一边因为往父节点拼接时你不可能既走左又走右。3.2 为什么返回值和答案要分开维护这是我刷这道题时卡最久的地方值得单独拎出来说。假设当前节点是node它的父节点是parent。如果parent想经过node继续往其他方向走那么从parent的视角看它只需要知道往 node 这个方向走最多能得到多大的收益。这个时候路径从parent出发进到node然后只能往node的某一个子方向继续走不可能同时走node的左右两边否则路径就分叉了不叫路径。所以dfs(node)的返回值必须是一条单链的最大值而ans记录的是可以拐弯的完整路径的最大值。两者服务对象不同返回值给父节点用ans给最终结果用。搞混这两个值是这题最常见的错误写法。3.3 关于初始值Integer.MIN_VALUE的选择ans初始化为Integer.MIN_VALUE而不是 0这里面有个很隐蔽的坑。假如整棵树所有节点都是负数比如三个节点值分别为-1, -2, -3那么最大路径和只能是从这三个里面挑一个最大的答案是 -1。如果ans初始化为 0代码会认为空路径的和 0 比任何负路径都大最终返回 0而正确答案是 -1。之前有不少人在这里翻车就是因为把ans初始化成了 0。严格来说题目要求路径至少包含一个节点所以初始值必须是一个不可能比任何真实答案大的数Integer.MIN_VALUE是最稳妥的选择。4. 实例推演用几个例子把递归跑通4.1 最简单的一棵三节点树先看一棵非常规整的树1 / \ 2 3手动推演一下。访问节点2leftGain 0rightGain 0currentPathSum 0 2 0 2更新ans 2返回2 max(0,0) 2。访问节点3同理ans max(2, 3) 3返回 3。访问节点1leftGain max(0, 2) 2rightGain max(0, 3) 3currentPathSum 2 1 3 6更新ans 6返回1 max(2,3) 4。最终结果是 6对应路径2 - 1 - 3。注意dfs(1)返回的是 4代表从根往下走的最大单链是1 - 3但全局答案是 6因为拐弯把左右两边都利用上了。4.2 全负数的极端情况再看一棵全是负数的树-3 / \ -2 -1节点-2currentPathSum -2ans -2返回 -2。节点-1currentPathSum -1ans max(-2, -1) -1返回 -1。节点-3leftGain max(0, -2) 0rightGain max(0, -1) 0currentPathSum 0 (-3) 0 -3ans保持 -1返回-3 max(0,0) -3。最终答案是 -1路径就是那个值为 -1 的单独节点。这个例子能很好说明为什么ans不能从 0 开始也说明leftGain max(0, dfs(...))这个裁剪操作在负数场景下如何发挥作用它让每个节点在拐弯时可以主动放弃两侧的负贡献只保留自己。4.3 稍微复杂的场景再来一棵稍微复杂的树10 / \ 2 -20 / \ / \ 7 5 1 -6节点7返回7ans 7。节点5返回5ans max(7,5) 7。节点2leftGain 7rightGain 5currentPathSum 7 2 5 14ans 14返回2 max(7,5) 9。这里返回值9对应路径2 - 7是一条单链给父节点10拼接用。节点1返回1ans不变。节点-6返回-6ans不变。节点-20leftGain max(0,1) 1rightGain max(0,-6) 0currentPathSum 1 (-20) 0 -19这个值不会超过当前ans但还是要算一下并比较。返回-20 max(1,0) -19。节点10leftGain max(0, 9) 9rightGain max(0, -19) 0currentPathSum 9 10 0 19ans max(14, 19) 19返回10 max(9,0) 19。最终答案是 19对应路径7 - 2 - 10。注意右子树整个是负收益区它被max(0, ...)裁剪掉了这是正确决策绕开负数比硬着头皮带上它强。4.4 某条子树内部有最优解根只是路过的看客还有一种情况需要想清楚最优路径可能完全不出现在某个子树的返回值里但仍然会被ans记录到。比如一棵树左子树内部有一条大正数路径但左子树根节点的值非常小导致往父节点传递的单链值并不大。这完全没问题因为左子树内部的完整路径在它自己的节点上更新ans时就已经被记录了。父节点只需要拿到一个适合自己的单链值并不需要知道子树内部的最优路径长什么样。这个特性正是返回值给上层拼接ans收集全局答案这套设计能生效的原因。5. 常见错误与排查技巧实录5.1 最容易踩的坑这道题我在不同阶段反复踩过几个坑列出来给大家避雷。第一个坑返回值写成了node.val leftGain rightGain。这样返回的就不是单链而是拐了弯的完整路径。父节点如果拿这个值去拼接相当于路径在子节点处已经拐过弯到父节点又拐一次路径就出现了分叉完全不符合定义。这种错误通常不会导致答案偏小反而会偏大而且很难通过小数据样例发现。第二个坑ans初始化为 0。前面已经分析过全负数时会返回错误答案 0。很多平台上的测试用例都包含全负数场景这个坑非常致命。第三个坑忘记处理空节点。在递归过程中子节点为null是常态如果不在一开始返回 0后面就会空指针异常。这道题的递归终止条件必须写在函数最前面。第四个坑把leftGain和rightGain裁剪逻辑写错。有的写法是Math.max(dfs(node.left), 0)放在返回语句里这样其实也没问题但容易跟return里的Math.max(leftGain, rightGain)搞混。建议在函数体里先算好再使用逻辑更清晰。5.2 我实际用的调试方法如果你发现答案不对又不想盯着代码干想可以在递归函数里临时加一段打印逻辑把每个节点的关键信息输出出来private int dfs(TreeNode node) { if (node null) return 0; int leftGain Math.max(0, dfs(node.left)); int rightGain Math.max(0, dfs(node.right)); int currentPathSum leftGain node.val rightGain; ans Math.max(ans, currentPathSum); int returnValue node.val Math.max(leftGain, rightGain); System.out.println(node node.val leftGain leftGain rightGain rightGain currentPathSum currentPathSum returnValue returnValue ans ans); return returnValue; }打印出来之后手动对照每个节点的currentPathSum和returnValue是否符合预期。尤其是看某个节点的返回值是否是一条单链这一点非常容易排查出返回值错误地拐了弯这类问题。我在调试的时候还会刻意为每个节点设计不同的场景左正右负、左负右正、左右都负、左右都正确保每种情况都覆盖到。5.3 复杂度分析时间复杂度是 O(n)因为每个节点只被访问一次递归过程中每个节点做常数次计算。空间复杂度是 O(h)h 是树的高度。递归调用栈的深度取决于树的高度最坏情况下树退化成一条链h n此时空间复杂度为 O(n)平均情况下是 O(log n)。这道题没法用迭代做得很优雅递归是树形结构最自然的遍历方式所以空间复杂度就是树高。6. 变体与延伸面试中的考法6.1 变体一二叉树直径二叉树直径问题是 124 题的近亲。区别在于124 题求的是节点值之和最大直径求的是路径上节点个数或边数最多。解法几乎一样只需要把贡献值从max(0, childGain)变成1 max(leftDepth, rightDepth)的形式然后在每个节点用leftDepth rightDepth更新全局答案。你会发现核心套路还是那套返回单链深度收集拐弯结果。6.2 变体二路径必须经过根节点如果把题目改成必须经过根节点就简单很多了因为拐弯中心被固定为根。此时答案就是root.val max(0, dfs(root.left)) max(0, dfs(root.right))不需要全局变量一次递归就能搞定。这个变体经常作为 124 题的热身题出现在面试中可以先做这个再做完整版。6.3 变体三N 叉树的任意路径最大和如果二叉树变成 N 叉树每个节点有多个孩子思路完全不变。dfs(node)还是返回从 node 往下走的最大单链值。只不过在更新currentPathSum时不再是左右两条链相加而是从所有孩子里选出正值贡献最大的两个加起来再加上node.val。这实际上是贪心路径在 N 叉树的某个节点处最多只能连接两条向下的链所以要挑收益最大的两个孩子。这个变体在面试中出现的频率不低考察的是对核心思路的理解是否够深而不是死记模板。6.4 延展思考如果节点值全是正数会怎样如果题目额外保证所有节点值都是正数那么max(0, ...)裁剪就永远不生效每个节点都会把左右两侧都带上。此时答案相当于整棵树的节点值之和减去某些不取的部分。不过题目没有这个限制所以裁剪逻辑不能省。这类如果条件变了代码哪里可以简化的问题面试官很喜欢追问平时刷题时可以多想一步。结尾刷完这道题我最大的体会是二叉树递归题的核心不是把遍历写出来而是想清楚每个递归函数到底返回什么。124题用一份十几行的代码把这个道理讲得明明白白——返回值是给父节点拼接的单链ans收集的是可以拐弯的完整路径两者分开维护答案自然就出来了。最后再分享一个小技巧遇到这种树上路径问题先别急着写代码。在纸上画一棵树随便选一个节点把经过它的路径拆成左边一条链 节点 右边一条链想清楚每条链往父节点能贡献什么思路就顺了。这个拆解动作我到现在做变体题时还在用确实管用。 
LeetCode 124这道题全称 Binary Tree Maximum Path Sum中文一般叫二叉树中的最大路径和在二叉树递归题里属于绕不开的经典。我第一次刷到它的时候被一个路径绕了很久因为题目允许路径从任意节点出发、到任意节点结束而且可以拐弯跟平时习惯的根到叶子完全不是一回事。这篇文章我把完整的思路、代码、踩坑都写出来想彻底吃透这道题的朋友可以一步步照着推。这道题解决的核心问题是给定一棵二叉树每个节点有权值可能是负数找到一条任意走向的路径让路径上所有节点的值加起来最大。它适合正在刷二叉树递归的人、准备算法面试的人还有想系统整理树形 DP 思路的人。看完之后你会发现这类题的代码其实很短难点全在状态定义上。1. 先从题目本身说起1.1 题面到底在问什么先翻译一遍题面给你一棵非空二叉树每个节点上有一个整数值可能为正也可能为负。你要找出一条路径使得路径经过的所有节点值之和最大返回这个最大值。这里有几个关键限定需要抠清楚路径可以从任意节点开始到任意节点结束不需要经过根节点。路径中每个节点只能经过一次不能走回头路。路径至少包含一个节点不能是空路径。一个节点只有左右两个子节点所以路径在某个节点处最多只能拐一次弯。很多人第一次看到任意节点到任意节点会懵心里想这到底怎么枚举二叉树里任意两个节点之间不是有唯一路径吗难道要枚举所有点对如果真去枚举点对复杂度就是O(n²)显然不是题目想考的。实际上这道题考的是如何在一次树形遍历中同时维护向下延伸的单链和可以拐弯的完整路径两类信息。把题目理解成在一棵树上找一条连续路径让路径权值和最大就对了。树的路径跟数组子数组最大的区别是数组是线性的路径不能跳树是分叉的路径在某个节点处可以选择从左子树来、到右子树去形成一次拐弯。1.2 为什么这道题是必刷经典刷题圈子里经常说二叉树递归有三座大山最大路径和、直径、最近公共祖先。124题能成为经典我觉得有三个原因。第一递归状态设计得非常典型。它要求你分清楚给父节点返回什么和自己局部能更新出什么答案这个区分在树形 DP 里反复出现。弄懂这一题后面做打家劫舍 III、监控二叉树、最长同值路径之类的题会顺很多。第二它对路径这个概念的理解要求很高。如果只知道路径是连续走的一段很容易写出只往一个方向走的错误代码。必须意识到路径可以在某个节点上拐弯而拐弯点恰恰就是路径上深度最小的那个节点。第三面试高频且衍生性强。很多公司会把这道题当基础题考然后立刻加限制比如如果节点值都是正数怎么做如果要求路径必须经过根节点怎么做如果改成求最长路径长度直径怎么做。2. 核心思路从后序遍历到状态定义2.1 先想清楚一件事路径为什么能拐弯在一棵二叉树里任意两个节点之间的路径是唯一的因为树中没有环。这条唯一路径可以看作向上走到某个公共祖先再向下走到目标节点。举个例子一棵树长这样1 / \ 2 3 / \ \ 4 5 6节点4到节点6的路径是4 - 2 - 1 - 3 - 6。这条路径在节点1处拐了一个弯左侧部分是4 - 2右侧部分是3 - 6中间夹着节点1。所以完整路径可以拆成三段从左子树向下延伸的一条链 拐弯节点本身 从右子树向下延伸的一条链。两侧的链可以退化为空也就是说路径可以只往一个方向走甚至只有一个节点。这个拆法非常关键因为它把任意两点路径变成了每个节点当拐弯中心的问题。我们只需要遍历每个节点算出以它为拐弯中心能组成的最大路径然后取全局最大值即可。2.2 递归状态怎么定义既然要以每个节点为拐弯中心那递归函数就需要知道从当前节点往下走能走出的最大单链值是多少。注意这里刻意强调单链因为只有单链才能作为完整路径的半边交给父节点拼接。我习惯把这个函数叫做dfs(node)含义是从 node 出发沿着子节点向下走到任意位置形成的单条链的最大节点值之和。所谓单条链就是路径只能一直往一个方向走不能分叉。比如从节点1出发可以走1 - 2可以走1 - 3 - 6但这些都是一条直线。那么dfs(node)怎么算它等于node.val max(dfs(node.left), dfs(node.right))等等这里需要处理一个细节如果某个子树返回的值是负数带上它只会让总和变小。比如dfs(node.left) -5那我还不如不选左子树让左半边为空。所以更严谨的写法是node.val max(0, dfs(node.left), dfs(node.right))也就是每个子树的贡献先和0取最大值负贡献直接丢弃。这个贡献和0取max的操作是整道题的核心思想之一。2.3 局部答案怎么更新现在有了单链值下一步就是在每个节点处计算经过该节点、可能拐弯的完整路径的最大值。刚才说过完整路径 左链 节点 右链。左链和右链都可以为空所以当前节点作为拐弯中心时最大完整路径为max(0, dfs(node.left)) node.val max(0, dfs(node.right))这个值只对当前节点有意义它不能再往上传递因为往上传递时路径只能作为一条单链不能两边都带着。如果父节点还要用你这边的结果它只能收到一条链不能收到一个V字形。所以整棵树的答案就是在所有节点的完整路径候选值里取最大值。用一个全局变量ans来记录每遍历到一个节点就更新一次。这里就是树形 DP 最常见的套路每个递归函数返回局部最优但可拼接的信息同时用一个外部变量收集全局最优但不可拼接的信息。前者给上层用后者作为最终答案。3. 代码实现与逐行解读3.1 最精简的 Java 代码先把代码贴出来然后逐行拆。class Solution { private int ans Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { dfs(root); return ans; } private int dfs(TreeNode node) { if (node null) { return 0; } int leftGain Math.max(0, dfs(node.left)); int rightGain Math.max(0, dfs(node.right)); int currentPathSum leftGain node.val rightGain; ans Math.max(ans, currentPathSum); return node.val Math.max(leftGain, rightGain); } }整个代码只有十几行但每一行都有讲究。root为空的情况题目不会给但递归过程中子节点会为空所以dfs的终止条件必须处理null返回 0 表示空子树对父节点没有任何贡献。leftGain和rightGain分别表示左右子树能给当前节点的最大单链贡献小于 0 就当 0 处理。这一点特别重要它隐含了一个决策如果某边是负收益我就不走那边让路径半边为空。currentPathSum是以当前节点为拐弯中心的完整路径和。注意这里用的是leftGain node.val rightGain不是node.val Math.max(leftGain, rightGain)。前者允许拐弯后者只是单链。ans维护所有拐弯中心里最大的那个就是最终答案。return node.val Math.max(leftGain, rightGain)是给父节点使用的单链值只能从左右两边选一边因为往父节点拼接时你不可能既走左又走右。3.2 为什么返回值和答案要分开维护这是我刷这道题时卡最久的地方值得单独拎出来说。假设当前节点是node它的父节点是parent。如果parent想经过node继续往其他方向走那么从parent的视角看它只需要知道往 node 这个方向走最多能得到多大的收益。这个时候路径从parent出发进到node然后只能往node的某一个子方向继续走不可能同时走node的左右两边否则路径就分叉了不叫路径。所以dfs(node)的返回值必须是一条单链的最大值而ans记录的是可以拐弯的完整路径的最大值。两者服务对象不同返回值给父节点用ans给最终结果用。搞混这两个值是这题最常见的错误写法。3.3 关于初始值Integer.MIN_VALUE的选择ans初始化为Integer.MIN_VALUE而不是 0这里面有个很隐蔽的坑。假如整棵树所有节点都是负数比如三个节点值分别为-1, -2, -3那么最大路径和只能是从这三个里面挑一个最大的答案是 -1。如果ans初始化为 0代码会认为空路径的和 0 比任何负路径都大最终返回 0而正确答案是 -1。之前有不少人在这里翻车就是因为把ans初始化成了 0。严格来说题目要求路径至少包含一个节点所以初始值必须是一个不可能比任何真实答案大的数Integer.MIN_VALUE是最稳妥的选择。4. 实例推演用几个例子把递归跑通4.1 最简单的一棵三节点树先看一棵非常规整的树1 / \ 2 3手动推演一下。访问节点2leftGain 0rightGain 0currentPathSum 0 2 0 2更新ans 2返回2 max(0,0) 2。访问节点3同理ans max(2, 3) 3返回 3。访问节点1leftGain max(0, 2) 2rightGain max(0, 3) 3currentPathSum 2 1 3 6更新ans 6返回1 max(2,3) 4。最终结果是 6对应路径2 - 1 - 3。注意dfs(1)返回的是 4代表从根往下走的最大单链是1 - 3但全局答案是 6因为拐弯把左右两边都利用上了。4.2 全负数的极端情况再看一棵全是负数的树-3 / \ -2 -1节点-2currentPathSum -2ans -2返回 -2。节点-1currentPathSum -1ans max(-2, -1) -1返回 -1。节点-3leftGain max(0, -2) 0rightGain max(0, -1) 0currentPathSum 0 (-3) 0 -3ans保持 -1返回-3 max(0,0) -3。最终答案是 -1路径就是那个值为 -1 的单独节点。这个例子能很好说明为什么ans不能从 0 开始也说明leftGain max(0, dfs(...))这个裁剪操作在负数场景下如何发挥作用它让每个节点在拐弯时可以主动放弃两侧的负贡献只保留自己。4.3 稍微复杂的场景再来一棵稍微复杂的树10 / \ 2 -20 / \ / \ 7 5 1 -6节点7返回7ans 7。节点5返回5ans max(7,5) 7。节点2leftGain 7rightGain 5currentPathSum 7 2 5 14ans 14返回2 max(7,5) 9。这里返回值9对应路径2 - 7是一条单链给父节点10拼接用。节点1返回1ans不变。节点-6返回-6ans不变。节点-20leftGain max(0,1) 1rightGain max(0,-6) 0currentPathSum 1 (-20) 0 -19这个值不会超过当前ans但还是要算一下并比较。返回-20 max(1,0) -19。节点10leftGain max(0, 9) 9rightGain max(0, -19) 0currentPathSum 9 10 0 19ans max(14, 19) 19返回10 max(9,0) 19。最终答案是 19对应路径7 - 2 - 10。注意右子树整个是负收益区它被max(0, ...)裁剪掉了这是正确决策绕开负数比硬着头皮带上它强。4.4 某条子树内部有最优解根只是路过的看客还有一种情况需要想清楚最优路径可能完全不出现在某个子树的返回值里但仍然会被ans记录到。比如一棵树左子树内部有一条大正数路径但左子树根节点的值非常小导致往父节点传递的单链值并不大。这完全没问题因为左子树内部的完整路径在它自己的节点上更新ans时就已经被记录了。父节点只需要拿到一个适合自己的单链值并不需要知道子树内部的最优路径长什么样。这个特性正是返回值给上层拼接ans收集全局答案这套设计能生效的原因。5. 常见错误与排查技巧实录5.1 最容易踩的坑这道题我在不同阶段反复踩过几个坑列出来给大家避雷。第一个坑返回值写成了node.val leftGain rightGain。这样返回的就不是单链而是拐了弯的完整路径。父节点如果拿这个值去拼接相当于路径在子节点处已经拐过弯到父节点又拐一次路径就出现了分叉完全不符合定义。这种错误通常不会导致答案偏小反而会偏大而且很难通过小数据样例发现。第二个坑ans初始化为 0。前面已经分析过全负数时会返回错误答案 0。很多平台上的测试用例都包含全负数场景这个坑非常致命。第三个坑忘记处理空节点。在递归过程中子节点为null是常态如果不在一开始返回 0后面就会空指针异常。这道题的递归终止条件必须写在函数最前面。第四个坑把leftGain和rightGain裁剪逻辑写错。有的写法是Math.max(dfs(node.left), 0)放在返回语句里这样其实也没问题但容易跟return里的Math.max(leftGain, rightGain)搞混。建议在函数体里先算好再使用逻辑更清晰。5.2 我实际用的调试方法如果你发现答案不对又不想盯着代码干想可以在递归函数里临时加一段打印逻辑把每个节点的关键信息输出出来private int dfs(TreeNode node) { if (node null) return 0; int leftGain Math.max(0, dfs(node.left)); int rightGain Math.max(0, dfs(node.right)); int currentPathSum leftGain node.val rightGain; ans Math.max(ans, currentPathSum); int returnValue node.val Math.max(leftGain, rightGain); System.out.println(node node.val leftGain leftGain rightGain rightGain currentPathSum currentPathSum returnValue returnValue ans ans); return returnValue; }打印出来之后手动对照每个节点的currentPathSum和returnValue是否符合预期。尤其是看某个节点的返回值是否是一条单链这一点非常容易排查出返回值错误地拐了弯这类问题。我在调试的时候还会刻意为每个节点设计不同的场景左正右负、左负右正、左右都负、左右都正确保每种情况都覆盖到。5.3 复杂度分析时间复杂度是 O(n)因为每个节点只被访问一次递归过程中每个节点做常数次计算。空间复杂度是 O(h)h 是树的高度。递归调用栈的深度取决于树的高度最坏情况下树退化成一条链h n此时空间复杂度为 O(n)平均情况下是 O(log n)。这道题没法用迭代做得很优雅递归是树形结构最自然的遍历方式所以空间复杂度就是树高。6. 变体与延伸面试中的考法6.1 变体一二叉树直径二叉树直径问题是 124 题的近亲。区别在于124 题求的是节点值之和最大直径求的是路径上节点个数或边数最多。解法几乎一样只需要把贡献值从max(0, childGain)变成1 max(leftDepth, rightDepth)的形式然后在每个节点用leftDepth rightDepth更新全局答案。你会发现核心套路还是那套返回单链深度收集拐弯结果。6.2 变体二路径必须经过根节点如果把题目改成必须经过根节点就简单很多了因为拐弯中心被固定为根。此时答案就是root.val max(0, dfs(root.left)) max(0, dfs(root.right))不需要全局变量一次递归就能搞定。这个变体经常作为 124 题的热身题出现在面试中可以先做这个再做完整版。6.3 变体三N 叉树的任意路径最大和如果二叉树变成 N 叉树每个节点有多个孩子思路完全不变。dfs(node)还是返回从 node 往下走的最大单链值。只不过在更新currentPathSum时不再是左右两条链相加而是从所有孩子里选出正值贡献最大的两个加起来再加上node.val。这实际上是贪心路径在 N 叉树的某个节点处最多只能连接两条向下的链所以要挑收益最大的两个孩子。这个变体在面试中出现的频率不低考察的是对核心思路的理解是否够深而不是死记模板。6.4 延展思考如果节点值全是正数会怎样如果题目额外保证所有节点值都是正数那么max(0, ...)裁剪就永远不生效每个节点都会把左右两侧都带上。此时答案相当于整棵树的节点值之和减去某些不取的部分。不过题目没有这个限制所以裁剪逻辑不能省。这类如果条件变了代码哪里可以简化的问题面试官很喜欢追问平时刷题时可以多想一步。结尾刷完这道题我最大的体会是二叉树递归题的核心不是把遍历写出来而是想清楚每个递归函数到底返回什么。124题用一份十几行的代码把这个道理讲得明明白白——返回值是给父节点拼接的单链ans收集的是可以拐弯的完整路径两者分开维护答案自然就出来了。最后再分享一个小技巧遇到这种树上路径问题先别急着写代码。在纸上画一棵树随便选一个节点把经过它的路径拆成左边一条链 节点 右边一条链想清楚每条链往父节点能贡献什么思路就顺了。这个拆解动作我到现在做变体题时还在用确实管用。