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

力扣题目链接 (opens new window)

题目描述

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

路径和 是路径中各节点值的总和。

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

示例 1：

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

示例 2：

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

提示：

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

思路

这道题的难点在于：路径可以从任意节点开始，到任意节点结束，不一定经过根节点。

路径的形态

对于任意节点，经过它的最大路径有几种形态：

1. 只有该节点自己
2. 该节点 + 左子树的某条路径
3. 该节点 + 右子树的某条路径
4. 该节点 + 左子树的某条路径 + 右子树的某条路径

关键观察：

第 4 种情况，路径呈"∧"形，左右都有。但是这条路径不能再往上延伸了（因为已经走到了拐点）。

递归思路

用后序遍历（左右中），对于每个节点：

1. 递归计算左子树能贡献的最大路径和
2. 递归计算右子树能贡献的最大路径和
3. 更新全局最大路径和（考虑"∧"形路径）
4. 返回"单边最大路径和"给父节点（只能选左或右）

为什么返回"单边"？

因为父节点需要和子节点形成一条路径，不能同时选左右两边（那样就有拐点了，无法再往上延伸）。

处理负数：

如果左子树或右子树的贡献是负数，不如不要，取 0。

模拟过程

以示例 2 为例：root = [-10,9,20,null,null,15,7]

后序遍历过程：

遍历叶子节点 15：

• 左子树贡献：0（空）
• 右子树贡献：0（空）
• 经过 15 的最大路径：15
• 返回给父节点：15

遍历叶子节点 7：

• 左子树贡献：0
• 右子树贡献：0
• 经过 7 的最大路径：7
• 返回给父节点：7

遍历节点 20：

• 左子树贡献：15
• 右子树贡献：7
• 经过 20 的最大路径："∧"形 = 15 + 20 + 7 = 42
• 更新全局最大值：42
• 返回给父节点：max(15, 7) + 20 = 35（只能选单边）

遍历叶子节点 9：

• 返回给父节点：9

遍历根节点 -10：

• 左子树贡献：9
• 右子树贡献：35
• 经过 -10 的最大路径："∧"形 = 9 + (-10) + 35 = 34
• 全局最大值仍是 42
• 由于是根节点，不需要返回

解题代码

class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int maxSum = INT_MIN;
        maxGain(root, maxSum);
        return maxSum;
    }
    
private:
    // 返回以node为起点的单边最大路径和
    int maxGain(TreeNode* node, int& maxSum) {
        if (node == nullptr) return 0;
        
        // 递归计算左右子树的最大贡献
        // 如果贡献为负，不如不要，取0
        int leftGain = max(maxGain(node->left, maxSum), 0);
        int rightGain = max(maxGain(node->right, maxSum), 0);
        
        // 更新全局最大路径和（"∧"形路径）
        int pathSum = node->val + leftGain + rightGain;
        maxSum = max(maxSum, pathSum);
        
        // 返回单边最大路径和给父节点
        return node->val + max(leftGain, rightGain);
    }
};

复杂度分析

• 时间复杂度：O(n)，每个节点访问一次
• 空间复杂度：O(h)，h 为树的高度，递归栈空间

其他语言

Python3

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        max_sum = float('-inf')
        
        def max_gain(node):
            nonlocal max_sum
            
            if not node:
                return 0
            
            # 递归计算左右子树的最大贡献
            left_gain = max(max_gain(node.left), 0)
            right_gain = max(max_gain(node.right), 0)
            
            # 更新全局最大路径和
            path_sum = node.val + left_gain + right_gain
            max_sum = max(max_sum, path_sum)
            
            # 返回单边最大路径和
            return node.val + max(left_gain, right_gain)
        
        max_gain(root)
        return max_sum

Java

class Solution {
    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);
        
        // 更新全局最大路径和
        int pathSum = node.val + leftGain + rightGain;
        maxSum = Math.max(maxSum, pathSum);
        
        // 返回单边最大路径和
        return node.val + Math.max(leftGain, rightGain);
    }
}

Go

func maxPathSum(root *TreeNode) int {
    maxSum := math.MinInt32
    
    var maxGain func(*TreeNode) int
    maxGain = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        
        // 递归计算左右子树的最大贡献
        leftGain := max(maxGain(node.Left), 0)
        rightGain := max(maxGain(node.Right), 0)
        
        // 更新全局最大路径和
        pathSum := node.Val + leftGain + rightGain
        maxSum = max(maxSum, pathSum)
        
        // 返回单边最大路径和
        return node.Val + max(leftGain, rightGain)
    }
    
    maxGain(root)
    return maxSum
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

JS

var maxPathSum = function(root) {
    let maxSum = -Infinity;
    
    const maxGain = (node) => {
        if (!node) return 0;
        
        // 递归计算左右子树的最大贡献
        const leftGain = Math.max(maxGain(node.left), 0);
        const rightGain = Math.max(maxGain(node.right), 0);
        
        // 更新全局最大路径和
        const pathSum = node.val + leftGain + rightGain;
        maxSum = Math.max(maxSum, pathSum);
        
        // 返回单边最大路径和
        return node.val + Math.max(leftGain, rightGain);
    };
    
    maxGain(root);
    return maxSum;
};

与代码随想录联系

这道题考察的是二叉树的后序遍历和递归思维。

在代码随想录 二叉树章节 中，详细讲过二叉树的遍历方式和递归三要素。

本题的关键点：

1. 后序遍历 — 需要先知道左右子树的结果，才能计算当前节点
2. 递归返回值的设计 — 返回"单边最大"而不是"全局最大"，这一点很多录友容易混淆
3. 负数处理 — 贡献为负不如不要，体现了贪心思想

很多录友第一次做这道题，会纠结"为什么返回单边"。

想清楚这个：递归函数的返回值是给父节点用的，父节点要和子节点连成一条路径，不能同时选左右（那样就分叉了）。

而全局最大路径可以是"∧"形，所以在递归过程中用一个全局变量记录。

这种"局部返回值"和"全局最优解"分开维护的模式，在树的题目中很常见，录友们要理解透彻。