124. 二叉树中的最大路径和#

从生活场景理解最大路径和#

想象你是城市水务工程师，需要找到供水网络中输水量最大的管道路径。这条路径可能有多个分支，但水流只能单向流动。类似地，在二叉树中寻找最大路径和，就是要找到连接任意节点的路径，使得节点值的总和最大。就像寻找输水能力最强的管道组合，这个路径可能隐藏在树的某个角落。

问题描述#

题目目标#

二叉树中的路径被定义为一条从树中任意节点出发，沿父子连接到达任意节点的序列。同一个节点在一条路径中至多出现一次，且路径至少包含一个节点。给定二叉树的根节点 root ，返回其中路径和的最大值。

示例 1#

输入： root = [-10,9,20,null,null,15,7] 输出： 42 二叉树示意：

 -10   
/      \
9     20
     /  \
    15  7

说明： 最大路径不一定经过根节点；这里最优路径是 15 -> 20 -> 7，路径和为 42。

补充说明#

• 二叉树通常使用层序数组表示，null 表示该位置没有节点。

问题解析#

LeetCode第124题要求：在二叉树中找到一条路径，使得路径上所有节点值之和最大。路径至少包含一个节点，且不需要经过根节点。例如：

输入：root = [-10,9,20,null,null,15,7] 输出：42（路径15→20→7的和）

关键挑战：

1. 路径可以是任意父子节点组成的链（不一定是根到叶子）
2. 节点值可能为负数，需要合理取舍路径
3. 最大路径可能完全隐藏在某个子树中

递归法：全局最优与局部贡献的博弈#

递归思路分解#

我们通过三层次递进思考破解这个难题：

1. 节点视角：每个节点能向上贡献的最大值是什么？
2. 路径组合：当前节点作为路径顶点时，最大和是多少？
3. 全局最优：如何持续追踪整个树中的最大路径和？

class Solution {
    // 全局最大路径和，初始化为最小整数，兼容“全负数树”场景
    int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        // 从根节点开始递归计算每个节点的“最大贡献值”并更新全局答案
        maxGain(root);
        // 返回整棵树的最大路径和
        return maxSum;
    }

    // 计算节点贡献值：返回该节点能提供的最大单向路径和
    private int maxGain(TreeNode node) {
        // 递归终止条件：空节点贡献值为 0
        if (node == null) return 0;

        // 递归计算左子树贡献；若为负则舍弃（取 0）
        int leftGain = Math.max(maxGain(node.left), 0);
        // 递归计算右子树贡献；若为负则舍弃（取 0）
        int rightGain = Math.max(maxGain(node.right), 0);

        // 以当前节点为“拐点”时可形成的新路径和（可同时连接左右子树）
        int priceNewPath = node.val + leftGain + rightGain;
        // 用该路径和更新全局最大值
        maxSum = Math.max(maxSum, priceNewPath);

        // 向父节点返回“单边最大贡献值”：当前节点 + max(左贡献, 右贡献)
        // 注意：向上只能走一条边，所以不能同时带上左右两边
        return node.val + Math.max(leftGain, rightGain);
    }
}

递归过程图解#

以二叉树[-10,9,20,null,null,15,7]为例：

     -10
     / \
    9  20      ← 最大路径和出现在这里（15+20+7=42）
      /  \
     15   7

递归执行过程：

1. 计算叶子节点15：贡献值15，更新maxSum=15
2. 计算叶子节点7：贡献值7，更新maxSum=15→7→15
3. 节点20：左贡献15，右贡献7，路径和=20+15+7=42，更新maxSum=42
4. 节点9：贡献值9，路径和9，不更新maxSum
5. 根节点-10：左贡献9，右贡献20的贡献（20+15=35），路径和=-10+9+35=34，不更新maxSum

最终最大路径和为42。

关键点解析#

1. 双重任务递归：每个递归既计算局部贡献值，又参与全局最大值的更新
2. 负数处理艺术：当子树贡献为负时果断舍弃（Math.max(贡献值, 0)）
3. 路径组合策略：节点作为路径顶点时，可以同时连接左右子树
4. 全局变量追踪：使用类变量maxSum实时记录当前找到的最大值

常见误区#

1. 认为最大路径必须经过根节点（实际上可能完全在右子树）
2. 忘记处理节点值为负的情况（负数贡献需要谨慎取舍）
3. 混淆节点贡献值与路径和的概念（贡献值只能选单边）
4. 没有初始化maxSum为Integer.MIN_VALUE（当所有节点为负时会出错）

实际应用#

1. 社交网络中的影响力传播路径分析
2. 交通规划中的最优运输路线选择
3. 电路设计中的最大信号强度路径
4. 金融投资中的最优收益链式决策

进阶思考#

1. 如何输出最大路径的具体节点序列？
2. 如果允许路径重复经过节点，算法该如何修改？
3. 当树结构动态变化时，如何高效维护最大路径和？
4. 在N叉树中如何求解最大路径和？

总结#

最大路径和问题揭示了算法设计中的三个重要维度：

1. 分治思维：将复杂问题分解为节点级的局部决策
2. 全局视野：通过巧妙的状态追踪把握整体最优
3. 边界处理：对负数等特殊情况的处理彰显算法健壮性

就像水管工寻找最大水流路径，我们需要在局部利益与全局最优之间找到完美平衡。这正是递归算法在树结构问题中展现的独特魅力。

1. 二叉树高频题解题模板
2. 递归思维训练专项题库
3. 大厂真题深度解析
4. 空间复杂度优化技巧大全

在这里，我们将一起修炼算法内功，成为代码世界的终极忍者！🗡️