我来给你讲解 LeetCode 第 124 题「二叉树中的最大路径和」。

题目描述

给定一个非空二叉树，返回其最大路径和。

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

示例：

输入：[-10,9,20,null,null,15,7]
   -10
   / \
  9  20
    /  \
   15   7
输出：42
解释：15 → 20 → 7 这条路径和最大，为 15+20+7=42

解题思路

第一步：理解什么是"路径"

在这道题中，"路径"不是必须从根到叶子，而是：

1. 可以是任意节点到任意节点的路径
2. 路径方向是单向的（不能有分叉）
3. 路径必须连续

关键理解：对于任意节点，经过该节点的最大路径和有三种情况：

• 只包含该节点本身
• 该节点 + 左子树的一部分
• 该节点 + 右子树的一部分
• 该节点 + 左子树的一部分 + 右子树的一部分

第二步：设计递归函数

我们需要一个递归函数，对于每个节点，计算：

1. 以该节点为起点向下延伸的最大路径和（只能选择左或右一边）
2. 更新全局最大路径和（可以包含左右两边）

递归函数定义：

def max_gain(node):
    # 返回以node为起点的最大路径和（只能向左或向右延伸）
    # 同时更新全局最大路径和

第三步：递归过程详解

对于每个节点：

1. 如果节点为空，贡献值为0
2. 递归计算左子树的最大贡献值（如果为负则取0）
3. 递归计算右子树的最大贡献值（如果为负则取0）
4. 计算经过当前节点的最大路径和 = 节点值 + 左贡献 + 右贡献
5. 更新全局最大值
6. 返回给父节点的贡献值 = 节点值 + max(左贡献, 右贡献)

第四步：具体步骤演示

以示例二叉树为例：

   -10
   / \
  9  20
    /  \
   15   7

节点15：

• 左贡献=0，右贡献=0
• 经过15的路径和=15
• 返回给父节点的贡献值=15

节点7：

• 左贡献=0，右贡献=0
• 经过7的路径和=7
• 返回给父节点的贡献值=7

节点20：

• 左贡献=15，右贡献=7
• 经过20的路径和=20+15+7=42 ← 全局最大值
• 返回给父节点的贡献值=20+max(15,7)=35

节点9：

• 左贡献=0，右贡献=0
• 经过9的路径和=9
• 返回给父节点的贡献值=9

根节点-10：

• 左贡献=9，右贡献=35
• 经过-10的路径和=-10+9+35=34
• 全局最大值仍为42

第五步：算法实现

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        self.max_sum = float('-inf')
        
        def max_gain(node):
            if not node:
                return 0
                
            # 递归计算左右子树的最大贡献值
            left_gain = max(max_gain(node.left), 0)  # 如果为负则取0
            right_gain = max(max_gain(node.right), 0)
            
            # 当前节点的路径和（可以包含左右子树）
            price_newpath = node.val + left_gain + right_gain
            
            # 更新全局最大值
            self.max_sum = max(self.max_sum, price_newpath)
            
            # 返回给父节点的贡献值（只能选择一边）
            return node.val + max(left_gain, right_gain)
        
        max_gain(root)
        return self.max_sum

第六步：复杂度分析

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

第七步：关键点总结

1. 区分两种路径：返回给父节点的路径（只能选一边）vs 全局最大路径（可以包含两边）
2. 负贡献处理：如果子树贡献为负，直接取0（相当于不选择该子树）
3. 后序遍历：需要先知道左右子树的结果，才能计算当前节点
4. 全局变量：使用全局变量记录遍历过程中的最大值

这个算法的核心思想是通过递归自底向上计算每个节点的贡献值，同时在递归过程中更新全局最大路径和。