二叉树中的最大路径和——后序遍历的全局变量技巧

老张2026/4/30大约 8 分钟

二叉树中的最大路径和——后序遍历的全局变量技巧

适读人群：Java 后端工程师、准备大厂面试的同学 | 阅读时长：约20分钟 | 难度：Hard

开篇故事

124 题是二叉树题目里 Hard 级别的经典。它的难点不是算法复杂，而是"思维转换"——如何把一个看起来需要枚举所有路径的问题，转换成一个简洁的后序递归。

我第一次看到这道题，想的是：路径可以从树中任意节点出发，到任意节点结束。节点数可以是几万，路径数是指数级别的，怎么枚举？

后来理解了这道题的核心思路：路径必然有一个"最高点"（即路径的最顶端节点），以这个最高点为中心，路径向左和向右延伸。对于每个节点，考虑它作为最高点时能达到的最大路径和，然后取所有节点里的最大值。这就把问题从"枚举路径"转化为"枚举最高点"，复杂度从指数级降到 O(n)。

这种思维——枚举决策点而不是枚举路径——在很多树的题目里都能用到，值得深入理解。

一、题目解析

题目：LeetCode 124. 二叉树中的最大路径和

二叉树中的路径被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点，且不一定经过根节点。

给你一个二叉树的根节点 root，返回其最大路径和。

示例：

输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3，路径和为 2 + 1 + 3 = 6

输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7，路径和为 15 + 20 + 7 = 42

约束：

树中节点数目在 [1, 3 * 10^4] 范围内
-1000 <= Node.val <= 1000

重要注意： 节点值可以为负数，所以路径不一定要延伸到叶节点。

二、解法一：暴力解法——枚举所有节点对

思路

找出所有节点对 (u, v)，计算从 u 到 v 的路径和，取最大值。但这样做复杂度是 O(n^2) 到 O(n^3)，实际上很难高效实现，仅作为思路展示。

更实用的暴力方法：对每个节点，用 DFS 计算以该节点为起点向下延伸的最大路径和，然后枚举每个节点作为路径的"最高点"。

class Solution {
    public int maxPathSum(TreeNode root) {
        int[] maxSum = {Integer.MIN_VALUE};
        getAllMaxGain(root, maxSum);
        return maxSum[0];
    }
    
    // 对每个节点，计算从它出发向下延伸的最大增益
    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);
        return node.val + Math.max(leftGain, rightGain);  // 只能选一侧
    }
    
    // 枚举每个节点作为最高点
    private void getAllMaxGain(TreeNode node, int[] maxSum) {
        if (node == null) return;
        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);
        maxSum[0] = Math.max(maxSum[0], node.val + leftGain + rightGain);
        getAllMaxGain(node.left, maxSum);
        getAllMaxGain(node.right, maxSum);
    }
}

这个版本有大量重复计算，时间复杂度 O(n^2)。

复杂度分析

时间复杂度：O(n^2)。对每个节点调用 maxGain，而 maxGain 本身是 O(n)。
空间复杂度：O(n)。递归栈。

三、解法二：后序遍历 + 全局变量（标准解法）

思路

核心思路：把"枚举每个节点作为最高点"的过程与"计算从每个节点向下的最大增益"的后序递归合并。

定义递归函数 maxGain(node)：返回以 node 为根的子树，从 node 出发向下延伸（只能走一侧）的最大路径和。

同时，在递归过程中，每到一个节点，就把它作为路径最高点，计算"左增益 + 节点值 + 右增益"，与全局最大值比较更新。

关键：向下延伸时只能选左或右（不能同时），因为路径是一条线段，不能分叉。但在计算"当前节点作为最高点的路径和"时，可以同时取左右两侧。

完整代码

class Solution {
    private int maxSum = Integer.MIN_VALUE;  // 全局最大路径和
    
    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }
    
    // 返回以 node 为起点，向下延伸的最大路径和（只能选一侧）
    private int maxGain(TreeNode node) {
        if (node == null) return 0;
        
        // 递归计算左右子树的最大增益
        // 如果增益为负，宁可不选（取 0）
        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);
        
        // 以当前节点为最高点的路径和 = 左增益 + 节点值 + 右增益
        int pathSum = node.val + leftGain + rightGain;
        maxSum = Math.max(maxSum, pathSum);
        
        // 向上返回时，只能选一侧（路径不能分叉），加上节点值
        return node.val + Math.max(leftGain, rightGain);
    }
}

复杂度分析

时间复杂度：O(n)。每个节点只被访问一次。
空间复杂度：O(n)。递归栈，最坏情况（链状树）O(n)。

提交结果：时间击败约 99% 用户，空间击败约 75% 用户。

四、解法三：最优解法——统一返回结构体（避免全局变量）

思路

全局变量在工程代码里是代码异味——如果 Solution 对象被复用，maxSum 会残留上次的值。更好的做法是把全局变量封装进递归返回值里，用 int[] 数组或者内部状态传递。

但 Java 的 int 是值传递，不能通过返回值直接修改外部变量。常见做法是用 int[] 数组（引用传递），或者如上面的代码用实例变量（确保每次调用前重置）。

另一种完全不用全局变量的方式：把 maxSum 作为数组参数传入递归，在递归内部更新。

Mermaid 图——路径和枚举思路

完整代码（无全局变量版本）

class Solution {
    public int maxPathSum(TreeNode root) {
        int[] maxSum = {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);
    }
}

这种写法函数是纯的（除了修改 maxSum[0]），但实际上 maxSum 数组还是作为"副作用容器"在使用，本质上和实例变量差不多。真正的函数式写法需要返回两个值（maxGain 和 maxPathSum），可以用内部类或 int[] 实现。

复杂度分析（同解法二）

时间复杂度：O(n)。
空间复杂度：O(n)。

五、举一反三

"枚举中间节点"模式

int result = MIN_VALUE;

int dfs(TreeNode node) {
    if (node == null) return /* base case */;
    int left = dfs(node.left);
    int right = dfs(node.right);
    
    // 以当前节点为中间节点，更新全局答案
    result = Math.max(result, /* 利用 left, right, node 的组合 */);
    
    // 返回值：从当前节点往上只能传递一侧信息
    return /* 单侧最优值 */;
}

六、踩坑实录

坑一：负节点值时忘记与 0 取最大

节点值可以是负数。如果左子树的最大增益是负数，不走左子树比走了更好（收益是 0）。必须用 Math.max(maxGain(node.left), 0) 而不是直接用递归结果。

坑二：把路径和的最大值和递归返回值搞混

递归返回的是"从当前节点出发，向下只走一侧"的最大增益。更新全局 maxSum 的是"以当前节点为最高点，左右两侧都选"的路径和。这两个值不同，一定要区分。

坑三：初始化 maxSum 为 0 而不是 Integer.MIN_VALUE

如果所有节点值都是负数，最大路径和也是负数（因为路径至少要包含一个节点）。初始化为 0 会导致错误地返回 0 而不是最大的负数。

坑四：单节点树的处理

对于只有一个节点的树，maxGain 返回 node.val，maxSum 也更新为 node.val，没有问题。但有人在递归里写了 if (node.left == null && node.right == null) return node.val，然后忘记更新 maxSum，导致叶节点没有参与全局比较。

坑五：全局变量多次调用时的状态污染

如果 Solution 实例被复用（比如测试框架可能复用），实例变量 maxSum 会保留上次调用的值。可以在方法开头重置 maxSum = Integer.MIN_VALUE，或者用 int[] 参数传递。LeetCode 平台每次新建 Solution 实例，不会有问题，但养成重置的习惯更安全。

七、总结

124 题是树的题目里"枚举中间节点"思路的经典案例。一旦理解了"每个节点作为路径最高点时的贡献计算"，代码就非常自然了。

关键思维点：路径和是一个全局概念，不能直接通过一次递归从某个方向"传递"到根节点。解决方式是：把"路径穿过当前节点"的情况局部处理（更新全局变量），然后向上只返回"单侧延伸"的信息（供父节点继续处理）。

全局变量的使用在这里是一个实用技巧，但在工程代码里要注意线程安全和状态重置。用 int[] 参数传递是更清洁的写法。