好的，我们这次来详细讲解 LeetCode 第 124 题：二叉树中的最大路径和（Binary Tree Maximum Path Sum）。

这是一道二叉树领域的困难题，它考察的是对二叉树遍历的深刻理解以及如何定义和计算路径和。我们循序渐进地来剖析它。

1. 题目描述

题目：
给定一个非空二叉树，每个节点都有一个整数值。找到一条路径，使得路径上所有节点的值之和最大。返回这个最大的和。

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

示例 1：

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

示例 2：

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

核心难点：
路径不是必须从根节点开始，到叶子节点结束。它可以只是树的一部分，甚至可能是一条“折线”（即路径有一个最高点，向左右两边延伸）。

2. 问题分析与关键思路

我们先来理解什么是“路径”。在二叉树中，路径主要有三种形态：

1. 左子树 - 根 - 右子树：这是最复杂的情况，路径像一个倒着的 "V"，它穿越了根节点。例如示例2中的 15 -> 20 -> 7。
2. 根 - 左子树（或根 - 右子树）：路径是一条直线，从根节点开始，只向左或只向右延伸。
3. 只有根节点：当所有子树的和都是负数时，最大路径可能就是单个节点本身。

我们的目标是找到所有可能路径中的最大和。

关键思路：后序遍历（DFS）

• 为什么是后序遍历（左 -> 右 -> 根）？
  因为要计算一个节点的最大路径和，我们必须先知道它的左右子树能提供多大的贡献。

• 如何定义“贡献”？
  我们定义一个递归函数，比如叫 maxGain(node)。这个函数的返回值是：以该节点为起点的、向下延伸的路径的最大和。

  • 这条路径必须是单向的，不能同时走左右两边（否则就无法被父节点使用）。
  • 如果子树的和是负数，我们宁愿不要它，即贡献为0。例如，节点值为-10，左子树贡献为-5，那么从该节点出发的最大路径可能就是它自己（-10），但加上-5会更小。所以对于父节点来说，这个节点的贡献应该是 max(node.val, node.val + leftGain, node.val + rightGain)？不，更准确地说，是 node.val + max(leftGain, rightGain)，并且这个值如果小于0，我们就返回0（表示不要这个分支）。

计算全局最大路径和

在递归函数中，对于每一个节点，我们都可以计算以该节点为最高点（路径转折点）的路径和。
这个路径和 = 节点值 + 左子树贡献 + 右子树贡献。

我们用另一个全局变量 maxSum 来记录遍历所有节点时，这个“以当前节点为最高点的路径和”的最大值。

3. 详细解题步骤

我们一步步拆解这个过程。

步骤 1：定义递归函数和全局变量

• 定义一个全局变量 max_sum，初始化为负无穷（-inf），因为节点值可能为负数。
• 定义一个递归函数 dfs(node)，它的作用是计算并返回 以 node 为起点的、向下延伸的最大路径和（贡献值）。

步骤 2：递归函数的逻辑（dfs(node)）

1. 基准情况：如果节点 node 为空，它的贡献值为 0。
2. 递归计算左右子树的贡献：
   • left_gain = max(dfs(node.left), 0) // 如果左子树的贡献是负数，我们就不取它（贡献为0）。
   • right_gain = max(dfs(node.right), 0)
3. 计算“以当前节点为最高点的路径和”：
   • 这条路径可以同时包含左右子树，因为它是以 node 为顶点的完整路径。
   • price_newpath = node.val + left_gain + right_gain
4. 更新全局最大值：
   • 比较 max_sum 和 price_newpath，更新 max_sum 为两者中的较大值。
5. 返回当前节点对父节点的贡献值：
   • 对于父节点来说，路径只能选择当前节点和左分支 或 当前节点和右分支，不能同时选两边。
   • 所以返回值为：node.val + max(left_gain, right_gain)。

步骤 3：启动递归并返回结果

• 从根节点开始调用 dfs(root)。
• 递归结束后，返回全局变量 max_sum。

4. 举例说明（以示例2为例）

树结构：

       -10
       / \
      9  20
         / \
        15  7

初始化 max_sum = -inf。

1. 递归到节点 15：

   • 左右子树为空，贡献为0。
   • price_newpath = 15 + 0 + 0 = 15。
   • 更新 max_sum = max(-inf, 15) = 15。
   • 返回给父节点（20）的贡献值：15 + max(0, 0) = 15。

2. 递归到节点 7：

   • 同理，price_newpath = 7。
   • 更新 max_sum = max(15, 7) = 15。
   • 返回贡献值 7。

3. 递归到节点 20：

   • 左子树贡献 left_gain = max(15, 0) = 15。
   • 右子树贡献 right_gain = max(7, 0) = 7。
   • price_newpath = 20 + 15 + 7 = 42。这是关键！
   • 更新 max_sum = max(15, 42) = 42。
   • 返回给父节点（-10）的贡献值：20 + max(15, 7) = 35。

4. 递归到节点 9：

   • 同理，price_newpath = 9。
   • 更新 max_sum = max(42, 9) = 42。
   • 返回贡献值 9。

5. 递归到根节点 -10：

   • 左子树贡献 left_gain = max(9, 0) = 9。
   • 右子树贡献 right_gain = max(35, 0) = 35。
   • price_newpath = -10 + 9 + 35 = 34。
   • 更新 max_sum = max(42, 34) = 42。（最大值仍然是42，没有被覆盖）
   • 返回贡献值：-10 + max(9, 35) = -10 + 35 = 25。（注意，这里即使是正数，对最终结果也无影响，因为以-10为顶点的路径和34小于42）

最终，全局 max_sum 为 42，返回结果。

5. 代码实现（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: Optional[TreeNode]) -> int:
        # 初始化全局变量，用一个容器来存储（如列表），以便在递归函数中修改
        max_sum = [float('-inf')]
        
        def dfs(node):
            if not node:
                return 0
            
            # 递归计算左右子树的最大贡献值
            # 只有在贡献值大于0时，我们才选取该分支
            left_gain = max(dfs(node.left), 0)
            right_gain = max(dfs(node.right), 0)
            
            # 计算以当前节点为“顶点”的路径和
            price_newpath = node.val + left_gain + right_gain
            
            # 更新全局最大路径和
            max_sum[0] = max(max_sum[0], price_newpath)
            
            # 返回当前节点能对外提供的最大贡献值
            return node.val + max(left_gain, right_gain)
        
        # 开始递归
        dfs(root)
        return int(max_sum[0])

代码要点：

• 使用 max(..., 0) 来舍弃负贡献的分支。
• price_newpath 用于计算完整路径（可包含左右子树），用于更新全局答案。
• 递归返回值是单边路径的最大和，用于提供给父节点计算路径。

6. 复杂度分析

• 时间复杂度：O(N)，其中 N 是二叉树中的节点个数。我们对每个节点只访问一次。
• 空间复杂度：O(H)，其中 H 是树的高度。空间复杂度主要取决于递归调用的栈空间。在最坏情况下（树退化为链表），空间复杂度为 O(N)。

7. 总结与升华

这道题的精髓在于区分两个概念：

1. 节点的贡献值：提供给父节点使用的、单向路径的最大和。这是递归函数的返回值。
2. 以节点为顶点的路径和：可以同时利用左右子树的、完整的路径和。这是用来更新全局答案的。

通过后序遍历，我们自底向上地计算每个节点的这两种值，最终高效地找到了看似复杂的“任意路径”的最大和。这种“分解问题，利用子树信息”的思想，是解决许多二叉树问题的核心。