LeetCode 124 - 二叉树中的最大路径和（Binary Tree Maximum Path Sum）

重点难题：本题是二叉树路径问题中的经典难题，需要理解后序遍历与递归返true回值的巧妙设计。

问题描述

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

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

示例 1:

输入：[1,2,3]
    1
   / \
  2   3
输出：6

示例 2:

输入：[-10,9,20,null,null,15,7]
   -10
   / \
  9  20
    /  \
   15   7
输出：42

解题思路

这道题的关键在于理解二叉树中的"路径"概念。路径可以是：

只包含一个节点
从一个节点向下到其子节点
从左子树某节点，经过父节点，再到右子树某节点（形成"倒V"形状）

核心思想：使用后序遍历（左-右-根）自底向上计算路径和，针对每个节点，我们需要考虑两个关键值：

当前节点的贡献值：节点自身值加上左右子树中较大的贡献值（如果子树贡献为负，则不选取）
经过当前节点的最大路径和：节点值加上左右子树的贡献值（如为负则视为0）

关键在于区分这两个概念：

贡献值用于向上传递给父节点，只能选择一条路径（左或右）
最大路径和用于更新全局最大值，可以同时包含左右路径

实现细节

定义一个全局变量 maxSum 来记录最大路径和，初始值设为最小整数
定义递归函数 maxGain，计算节点的最大贡献值
对于每个节点，计算其左右子树的最大贡献值
如果贡献值为负，将其设为0（不选择这条路径）
计算经过当前节点的路径和，并更新全局最大值
返回当前节点的最大贡献值（只能选左或右子树中的一条）

代码实现

func maxPathSum(root *TreeNode) int {
    // 初始化最大和为最小整数
    maxSum := math.MinInt32
  
    // 定义递归函数计算节点的最大贡献值
    var maxGain func(node *TreeNode) int
  
    maxGain = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
      
        // 递归计算左右子树的最大贡献值
        leftVal := maxGain(node.Left)
        rightVal := maxGain(node.Right)
      
        // 如果子树贡献为负，则不选取
        if leftVal < 0 {
            leftVal = 0
        }
      
        if rightVal < 0 {
            rightVal = 0
        }
      
        // 计算经过当前节点的路径和，并更新全局最大值
        priceVal := leftVal + rightVal + node.Val
        if priceVal > maxSum {
            maxSum = priceVal
        }
      
        // 返回节点的最大贡献值（只能选左或右子树中的一条）
        return max(leftVal, rightVal) + node.Val
    }
  
    maxGain(root)
  
    return maxSum
}

复杂度分析

时间复杂度：O(N)，其中 N 是二叉树中的节点数。每个节点只被访问一次。
空间复杂度：O(H)，其中 H 是二叉树的高度。空间复杂度主要取决于递归调用的栈空间。

关键收获

路径定义的理解：二叉树中的路径不一定要从根开始或结束，但必须是连续的。
后序遍历应用：通过后序遍历可以自底向上收集路径信息。
递归设计巧妙性：递归函数的返回值（节点贡献值）与函数内更新的全局变量（最大路径和）分别服务于不同目的。
路径选择策略：对于负贡献值的子树，选择不纳入路径可以获得更大的路径和。