LeetCode第124题_二叉树中的最大路径和

@蓝莓果粒茶

1991人浏览 · 2025-04-02 02:00:00

@蓝莓果粒茶 · 2025-04-02 02:00:00 发布

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

题目描述

路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点，且不一定经过根节点。

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

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

难度

困难

题目链接

点击在LeetCode中查看题目

示例

示例 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

解题思路

方法一：递归（后序遍历）

这道题的关键是理解二叉树中的路径概念。路径可以从任意节点开始，到任意节点结束，但不能重复经过同一个节点。最大路径和可能经过根节点，也可能不经过根节点。

关键点：

对于每个节点，计算以该节点为根的子树中的最大路径和
区分"单边最大路径和"和"包含左右子树的最大路径和"
使用后序遍历，自底向上计算路径和

具体步骤：

定义一个全局变量maxSum，用于记录最大路径和
编写一个递归函数maxGain，计算以当前节点为根的子树的最大贡献值（单边最大路径和）
在递归函数中：
- 计算左子树的最大贡献值（如果为负，则取0）
- 计算右子树的最大贡献值（如果为负，则取0）
- 计算经过当前节点的最大路径和 = 当前节点值 + 左子树最大贡献值 + 右子树最大贡献值
- 更新全局最大路径和maxSum
- 返回当前节点的最大贡献值 = 当前节点值 + max(左子树最大贡献值, 右子树最大贡献值)
调用递归函数，返回maxSum

时间复杂度：O(n)，其中n是二叉树的节点数，每个节点只会被访问一次
空间复杂度：O(h)，其中h是二叉树的高度，递归调用栈的最大深度为h

图解思路

递归过程分析表

节点	节点值	左子树最大贡献值	右子树最大贡献值	经过该节点的最大路径和	该节点的最大贡献值	说明
节点7	7	0	0	7	7	叶子节点，左右子树贡献值为0
节点15	15	0	0	15	15	叶子节点，左右子树贡献值为0
节点20	20	15	7	42	35	经过该节点的最大路径和=20+15+7=42，最大贡献值=20+max(15,7)=35
节点9	9	0	0	9	9	叶子节点，左右子树贡献值为0
节点-10	-10	9	35	34	25	经过该节点的最大路径和=-10+9+35=34，最大贡献值=-10+max(9,35)=25

路径分析表

路径	路径和	是否为有效路径	说明
15 -> 20 -> 7	42	是	经过节点20的最大路径和
9 -> -10 -> 20	19	是	从9到20的路径
9 -> -10 -> 20 -> 15	34	否	路径不能同时包含-10的左右子树
9	9	是	单节点路径
-10	-10	是	单节点路径

代码实现

C# 实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    private int maxSum = int.MinValue;
    
    public int MaxPathSum(TreeNode root) {
        MaxGain(root);
        return maxSum;
    }
    
    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);
    }
}

Python 实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        self.max_sum = float('-inf')  # 初始化最大路径和为负无穷
        
        def max_gain(node):
            if not node:
                return 0
                
            # 递归计算左右子树的最大贡献值
            # 只有在最大贡献值大于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
            
            # 更新全局最大路径和
            self.max_sum = max(self.max_sum, path_sum)
            
            # 返回节点的最大贡献值
            return node.val + max(left_gain, right_gain)
            
        max_gain(root)
        return self.max_sum

C++ 实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int maxSum = INT_MIN;
        maxGain(root, maxSum);
        return maxSum;
    }
    
private:
    int maxGain(TreeNode* node, int& maxSum) {
        if (!node) {
            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);
    }
};

执行结果

C# 实现

执行用时：96 ms
内存消耗：40.2 MB

Python 实现

执行用时：84 ms
内存消耗：22.3 MB

C++ 实现

执行用时：20 ms
内存消耗：27.5 MB

性能对比

语言	执行用时	内存消耗	特点
C#	96 ms	40.2 MB	执行速度适中，内存消耗较高
Python	84 ms	22.3 MB	执行速度适中，内存消耗较低
C++	20 ms	27.5 MB	执行速度最快，内存消耗适中

代码亮点

🎯 使用后序遍历递归计算最大路径和，思路清晰
💡 巧妙区分"节点的最大贡献值"和"经过节点的最大路径和"两个概念
🔍 通过取最大值为0来处理负值节点，避免负值拖累路径和
🎨 全局变量与递归函数结合，代码结构简洁高效

常见错误分析

🚫 没有正确理解路径的定义，导致计算错误
🚫 忽略了负值节点的处理，没有取最大值为0
🚫 混淆了"节点的最大贡献值"和"经过节点的最大路径和"
🚫 没有考虑单个节点作为路径的情况

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
递归（后序遍历）	O(n)	O(h)	时间复杂度低，思路清晰	递归调用可能导致栈溢出
迭代（使用栈）	O(n)	O(n)	避免递归调用栈溢出	实现复杂，不直观