我把这道题放在刷题计划第168天来做说实话第一眼看到最大路径和四个字我还以为又是求根节点到叶子节点的最大值。真正动手写的时候才发现这题的路径定义要比我想的宽得多——它允许你从任意节点出发沿着父子连接走到任意节点结束路径可以斜着穿过某个节点甚至可以完全不过根。这一下就把难度拉上来了因为你要处理的不是一个方向的递归结果而是节点左右两边到底能贡献多少的问题。做LeetCode-124这题最核心的知识点就是递归但和单纯的遍历二叉树不一样这里的递归返回值得经过精心设计它既要服务于父节点的计算又要参与全局最大值的更新。很多人卡在这道题上不是不会写递归而是搞不清递归函数返回什么和全局答案怎么更新这两件事的区别。这篇文章我会把自己当时的思考过程、最后落地的代码、以及调试时踩过的坑完整写下来希望能帮到正在刷二叉树系列的朋友。1. 这道题真正的难点最大路径和是个横跨式结果1.1 先看题目到底在求什么题目给了一棵二叉树每个节点上有一个整数值可能是正数也可能是负数。你要找出一条路径使得路径上所有节点值之和最大。这里的路径定义有几个关键点路径可以从任意节点出发到任意节点结束。路径必须沿着父子之间的连接走不能跳。一个节点在路径中只能出现一次。路径至少包含一个节点。举个例子如果树是[1,2,3]也就是根节点为1左孩子2右孩子3那最大路径和就是2 1 3 6。注意这里路径经过了根节点连接了左右两个孩子。再看一个更典型的例子树是[-10,9,20,null,null,15,7]也就是根节点是-10左孩子9右孩子2020的左孩子15右孩子7。肉眼扫一遍最值钱的路径是15 - 20 - 7这条路径根本不经过根节点-10总和是42。如果你脑子里只有从根出发的路径那这道题就直接做错了。所以这个题的本质是在任何一棵子树里路径可能穿过某个节点把它的左子树贡献、自身值、右子树贡献拼在一起也可能只在某一侧向下延伸。我们要找的就是所有可能的穿过节点而形成的路径中的最大值。1.2 为什么左右子树最大路径这个直觉会失败我看到不少题解在讲这道题的时候会说求左子树的最大路径和求右子树的最大路径和。这句话很有误导性。我第一版代码就是按这个思路写的结果样例都过不了。原因在于父节点在利用子节点信息时只允许从子节点那里借一条单边的路径。什么叫单边就是从某个子树的根节点出发只往左走或者只往右走一路向下延伸不回头。为什么必须是单边因为父节点要把这条路径和自己拼起来构成一条完整的路径时子树的路径必须有一个端点能继续连到父节点上。如果子节点返回的是穿过它的最大路径和那条路径可能已经横跨了它的左右子树父节点再往上一接路径就分叉了这在二叉树里是不合法的。举一个很实在的反例。假设一棵树根节点是1左孩子是-2右孩子是-3左孩子的左右孩子都是10。那么左子树内部的最大路径是10 - -2 - 10 18这个值确实很大。但父节点1需要的是从左孩子往下走的一条通路它只能选择10 - -2或者-2 - 10也就是从-2出发往某一侧延伸的单边路径值是10 (-2) 8或8。父节点如果把18直接拿过来拼接路径就变成了10 - -2 - 10 - 1这显然不合法。所以这道题的第一步突破就是认识到递归函数返回的应该是一个单边最大贡献值而不是子树内部最大路径和。这两个概念是彻底理解本题的分水岭。2. 把递归函数拆成两个使命一个向上汇报一个全局记牌2.1 一个节点在递归里扮演的两个角色如果你仔细观察上面说的谬误会发现每个节点其实同时承担了两个任务任务A作为路径终点链的某个中间段把从自己向下延伸到某一侧的最大贡献值返回给父节点帮助父节点拼出更长的路径。任务B作为路径最高点把经过自己、连接左右两边的最优路径和计算出来去更新全局答案。任务A对应的就是递归函数的返回值任务B对应的则是我们在递归过程中维护的一个全局变量。很多人写不出这题就是因为没有在代码层面把这两个任务分开。一个返回一个记录两者各司其职代码就会非常清晰。用生活化的类比来说每个节点就像一家加盟商它既要向总部父节点汇报自己这一侧单线生意最多能赚多少又在本地偷偷算一笔如果我把左右两家店连接起来一次性生意最多能赚多少后者直接上报给总部不代表加盟商自己能不能干而是让总部知道历史最高纪录。2.2 贡献值公式的推导过程先说贡献值contribution这个概念。对于任意一个节点node它的单边贡献值定义为从node出发沿着左孩子或右孩子方向一路向下行走能获得的最大路径和包含node自身。这个定义要求只能选一条边往下走不能左右都选。它对应的递归公式是singleGain(node) node.val max(singleGain(node.left), singleGain(node.right))但有一个很关键的细节如果某个孩子的贡献值是负数那还不如不选它。因为负数只会让总路径和变小而路径本身允许从任意节点开始没必要拖着一个负数的尾巴。所以公式要修正为singleGain(node) node.val max(max(singleGain(node.left), 0), max(singleGain(node.right), 0))换句话说每个分支在参与贡献之前先过一个0的门槛。这个max(..., 0)的写法正是这道题优美的地方之一它把可选这个语义直接写进了公式里。而任务B的全局更新公式是maxPathSum(node) max(maxPathSum(node.left), maxPathSum(node.right), node.val max(singleGain(node.left), 0) max(singleGain(node.right), 0))也就是说经过当前节点、并把它作为最高点的完整路径等于左边的正向贡献 自身值 右边的正向贡献。因为当前节点是最高点所以左右两边都可以接上不需要考虑向上延伸的问题。这个值只用来更新全局答案不返回给父节点。说到这里核心思路已经完整了递归函数向下走得是单边贡献向上汇报的也是单边贡献全局答案则是拿左右贡献都选上的结果去碰运气。理解了这句话这题就算真正掌握了。2.3 后序遍历顺序先算孩子再算自己整个递归过程天然是后序遍历因为你要先拿到左右孩子的贡献值才能计算当前节点的贡献值和路径和。这也是二叉树递归题里最常见的一种依赖关系。很多初学者会试图用前序遍历来写这道题结果发现左右孩子的值还没算出来根本没法计算当前节点的贡献代码直接卡壳。记住凡是节点值需要聚合孩子信息的题目几乎都是后序遍历。这一点在二叉树的最大路径和二叉树的最大深度二叉树直径等题目里都是通用的。后序遍历还有一个隐藏的好处你可以保证每个节点只被访问一次。因为路径最多穿过每个节点一次整个算法的时间复杂度就是O(N)其中N是节点总数。对于树结构问题这个复杂度已经是最好的情况了不需要额外的优化。3. 完整代码实现与一次递归过程的逐步推演3.1 Java实现全局变量加递归函数下面是我最终提交的Java版本代码结构上没有多余的修饰每一行都有明确的分工/** * Definition for a binary tree node. * public 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 { // 全局答案初始化为最小整数因为节点值可能是负数 private int maxSum Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { maxGain(root); return maxSum; } // 返回从当前节点出发向某一侧延伸所能获得的最大贡献值 private int maxGain(TreeNode node) { if (node null) { return 0; } // 后序遍历先算左右孩子 int leftGain Math.max(maxGain(node.left), 0); int rightGain Math.max(maxGain(node.right), 0); // 任务B经过当前节点的完整路径和用它更新全局最大值 int currentPathSum node.val leftGain rightGain; maxSum Math.max(maxSum, currentPathSum); // 任务A返回单边最大贡献值给父节点 return node.val Math.max(leftGain, rightGain); } }这段代码有几个值得注意的细节maxSum必须初始化为Integer.MIN_VALUE而不是0。因为如果整棵树所有节点都是负数合法的最大路径和也必然是负数初始化为0会直接导致答案错误。递归出口返回0这里的0也有讲究空节点没有贡献所以返回0而在父节点那里Math.max(maxGain(node.left), 0)已经做了负数剪枝所以即使函数内部返回了负数外部也会把它当作0处理。我是先调maxGain(root)然后返回maxSum这样一遍后序遍历就完成了所有计算不需要额外遍历。实际提交到LeetCode时间在1ms左右空间约44MB这已经是非常标准的答案了。如果你是用Python写的思路上完全一样只是把类的私有成员换成了非局部变量或者列表包一层但概念不能变。3.2 用一个具体例子完整走一遍递归我们还是用上面那个例子[-10,9,20,null,null,15,7]结构是-10 / \ 9 20 / \ 15 7从根节点-10开始调用maxGain(-10)。先算左孩子9maxGain(9)调用后它的左右孩子都是null返回0所以leftGain 0, rightGain 0。currentPathSum 9 0 0 9更新maxSum 9。然后返回9 max(0,0) 9。再算右孩子20进入maxGain(20)。继续算它的左孩子15maxGain(15)得到左右贡献都是0currentPathSum 15更新maxSum max(9,15) 15返回15。右孩子7同理currentPathSum 7此时maxSum还是15返回7。回到节点20leftGain max(15,0) 15rightGain max(7,0) 7。currentPathSum 20 15 7 42更新maxSum 42。返回20 max(15,7) 35。回到根节点-10leftGain max(9,0) 9rightGain max(35,0) 35。currentPathSum -10 9 35 34比42小不更新。返回-10 max(9,35) 25。最终maxSum 42。这个42正是路径15 - 20 - 7的和完美命中预期。注意这个过程中根节点虽然返回了25给上层但它的路径和34并没有更新全局答案这就是向上汇报单边贡献、全局记录完整路径两个使命分开的典型体现。3.3 复杂度与常见边界情况时间复杂度是O(N)每个节点恰好访问一次。空间复杂度是O(H)H是树的高度由递归调用栈决定。最坏情况是树退化成链表高度为N递归深度达到N也就是热搜词里反复出现的写二叉树程序时为什么总是报运行时错误的一个主要来源——栈溢出。关于这个问题我在第4部分会详细展开。边界情况有三类我在测试的时候都专门验证过单节点树[1]答案就是1。全负数树[-1,-2,-3]答案应该是 -1也就是单节点路径。如果全局变量初始化为0这里就会错。空树LeetCode这题默认至少有一个节点所以不用单独处理但如果你在本地测试空树maxGain(null)返回0maxSum会保持Integer.MIN_VALUE但这不算是这题的输入范围。4. 刷题时最容易踩的运行时错误栈溢出、空指针与初始化陷阱4.1 递归深度过大导致的栈溢出StackOverflowError这道题本身是树形结构通常递归深度不会太大。但有一个常见的变形输入树是单链结构比如每个节点只有一个右孩子深度达到几万个节点。这时候如果直接递归JVM的默认调用栈深度通常在几千层到一万层之间根本扛不住程序会直接抛出StackOverflowError。我在本地测试时造了一棵10000层的单链表树一跑直接栈溢出。LeetCode的测试用例通常不会这么极端但理解这个问题仍然很重要。你可以用这样的小工具验证TreeNode generateChain(int n) { TreeNode dummy new TreeNode(0); TreeNode cur dummy; for (int i 1; i n; i) { cur.right new TreeNode(i); cur cur.right; } return dummy.right; }如果真遇到上万层的树有两条路可以走把递归改成显式迭代 后序遍历使用栈模拟调用过程。用Morris遍历的变体但这种题很少出现实际工程意义也不大。从我个人的刷题经验来看掌握递归写法、明白后序依赖的推演方式比直接上迭代写法重要得多。因为面试官更看重思路是否清晰而不是你能否用迭代硬啃一个深度极端的数据。4.2 空指针异常递归内部到底要不要判空还有一个常见的报错场景在递归过程中你可能会写出类似node.left.val这样的代码结果node.left是null直接抛NullPointerException。这道题的代码里我们通过递归函数的天然出口规避了这个问题——当node为null时立即返回0上层就不需要再访问node.left了。但如果你在递归函数里额外写了针对孩子节点的访问逻辑比如if (node.left.val 0) { ... }那就有空指针风险了。正确做法是把判空与取值/递归分开先看当前节点是否为空为空就直接返回再看孩子节点是否存在如果需要访问则通过调用递归函数它内部会处理null来间接完成。一句话概括凡是递归函数能接收null的你就没必要在调用前判空但你在访问任何节点的字段之前必须确保这个节点不是null。这两件事别混在一起想。4.3 全局答案初始化的隐蔽陷阱这题的初始值我见到过三个版本初始化写法结果int maxSum 0;全负数树时答案错int maxSum Integer.MIN_VALUE;正确int maxSum Integer.MAX_VALUE;完全错误为什么0不对因为如果你的树里全是负数任何一个节点单独作为路径都比0小但路径又必须非空所以最终答案必然小于0。初始化成0之后所有节点的currentPathSum都比0小maxSum永远是0答案自然就错了。那为什么Integer.MAX_VALUE也不行因为最大值初始化为最大整数会导致任何路径和都比它小答案永远是初始值本身。这属于低级错误但我确实见过有人这么写。正确思路是全局答案的初始值应该取一个比所有可能答案都小的值。路径和的最大值是所有节点值之和的上限最小值理论上可以是节点数 * 最小节点值但因为节点值范围是[-1000, 1000]用Integer.MIN_VALUE是绝对安全的。这一行初始化看似不起眼实际上直接决定了全负数用例能不能过。5. 进阶扩展面试官如果继续追问你怎么接得住5.1 如何打印出最大路径的节点序列很多面试官在让你求完值之后会追加一个问题能不能把取得最大路径的那条路径打印出来这时候只在递归中记录最大值是不够的你还需要记录哪条路径产生了这个最大值。一个可行的思路是额外维护两个字段——bestLeftPoint和bestRightPoint分别记录产生最大路径和的那个节点的左右端点。当currentPathSum更新maxSum时同步记录当前节点以及它左、右贡献的来源端点。然后在递归结束后从当前记录的端点出发向左右子树回溯拼接路径。这个方案实现起来细节比较多核心在于递归函数在返回单边贡献时同时返回这个贡献对应的末端节点。我建议你在纸上先把[1,2,3]这个例子画一遍理解路径拼接的方式再动手写代码。这里提供一个简化版的Java伪码思路private int maxGainWithPath(TreeNode node, ListTreeNode path) { if (node null) return 0; // 左子树、右子树同样递归 int leftGain maxGainWithPath(node.left, leftPath); int rightGain maxGainWithPath(node.right, rightPath); // 如果leftGain 0就不拼左端点rightGain同理 // 更新maxSum时根据选中的左右贡献来源记录端点节点 // 返回单边贡献时根据左右谁更大决定把哪个子路径延伸到当前节点 }如果你只是希望先掌握本题的核心思想那打印路径可以先放一放把贡献值和全局答案这两个概念彻底吃透再去做这个扩展。5.2 不依赖全局变量的写法用结果类替代全局变量写法虽然简洁但有些面试官不喜欢类里带一个可变成员。一个替代方案是用一个长度为1的数组或者自定义结果类来承载答案。Java代码可以这样写class Solution { public int maxPathSum(TreeNode root) { int[] maxSum new int[]{Integer.MIN_VALUE}; maxGain(root, maxSum); return maxSum[0]; } private int maxGain(TreeNode node, int[] maxSum) { if (node null) return 0; int leftGain Math.max(maxGain(node.left, maxSum), 0); int rightGain Math.max(maxGain(node.right, maxSum), 0); maxSum[0] Math.max(maxSum[0], node.val leftGain rightGain); return node.val Math.max(leftGain, rightGain); } }用int[]而不是int的原因很简单Java方法传参是值传递直接传int进去递归内部修改不会反映到外部。换成数组实际上传的是数组引用修改数组元素才能共享状态。这个技巧在很多递归题里都适用比如求二叉树最大深度的迭代版本也可能用到类似思路。另外如果你用C写完全可以用int ans作为引用参数传进去会简洁不少。Python的话可以写self.maxSum作为实例属性或者把maxSum放进一个列表[0]。原理是相通的。5.3 从二叉树到多叉树的推广这道题的思路完全可以扩展成N叉树版本。在N叉树中路径的定义依然不变但经过当前节点的完整路径变成了当前节点值 所有孩子中贡献最大的两个记作top1和top2。也就是说在N叉树里你需要把孩子节点贡献值从大到小排序选择最大的两项作为路径的左右分支。如果孩子贡献值为负数就相当于不选。这种问题在一些公司的面试里也会出现核心逻辑跟二叉树的完全一致唯一的差异是把Math.max(leftGain, rightGain)改成在所有孩子的贡献中选前两名。实现时可以用一个优先队列或者两次循环找最大和次大值。int top1 0, top2 0; for (Node child : node.children) { int gain Math.max(maxGain(child, maxSum), 0); if (gain top1) { top2 top1; top1 gain; } else if (gain top2) { top2 gain; } } maxSum[0] Math.max(maxSum[0], node.val top1 top2); return node.val top1;这就是整个题目的完整延伸。实际写下来你会发现掌握了二叉树的这个递归结构N叉树的版本几乎不需要新的知识只是在取舍上有略微的调整。反过来如果你能把N叉树版本也写出来面试官对你的印象会明显加分。这道题我刷完最大的感受是递归题的瓶颈不在于语法而在于语义。当你把一个节点在系统中的职责想清楚了向上汇报什么、全局记录什么代码就是按着职责一行一行翻译出来而已。后序遍历、全局变量、0门槛剪枝这三个要素串起来LeetCode-124就彻底通透。如果你现在正卡在不知道递归该返回什么的阶段试着用我这个办法先画出节点的两个角色再填空式地写代码会顺很多。