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

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

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

给你一个二叉树的根节点 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 * 10000]
-1000 <= Node.val <= 1000

思考 第1步 分析:

题目给出的信息是：求二叉树中的最大路径和，路径不需要经过根节点，但至少包含一个节点。路径中的每个节点最多出现一次。

思考 第2步 提取信息:

1. 路径定义：节点序列，相邻节点间有边相连
2. 节点限制：每个节点在路径中最多出现一次
3. 路径要求：至少1个节点，不必过根节点
4. 数据范围：节点数[1, 30000]，节点值[-1000, 1000]
5. 目标：找出最大路径和

剩余步骤：19

思考 第3步 明确目标:

需要设计一个算法，遍历整个二叉树，找出所有可能的路径，并计算它们的和，返回最大值。关键是要处理好路径的选择问题。

剩余步骤：18

思考 第4步 开始推理:

这是一个需要用递归解决的问题。对于每个节点，我们需要考虑：

1. 以该节点为转折点的路径（左子树->节点->右子树）
2. 将该节点接入父节点路径的情况（节点+左子树 或 节点+右子树）

剩余步骤：17

思考 第5步 推理:

关键在于理解每个节点可能有两种贡献方式：

1. 作为路径的一部分向上提供（单边最大值）
2. 作为连接点连接左右子树（整体最大值）

剩余步骤：16

思考 第6步 推理:

递归函数需要返回两个值：

1. 以当前节点为端点的最大路径和（用于向上贡献）
2. 经过当前节点的最大路径和（用于更新全局最大值）

剩余步骤：15

反思

目前的思路是正确的，但需要注意处理负数节点值的情况，因为负数可能导致路径和减小。

思考 第7步 推理:

对于每个节点的处理逻辑：

1. 计算左子树的最大贡献值
2. 计算右子树的最大贡献值
3. 更新全局最大值（左贡献+当前节点+右贡献）
4. 返回节点的最大贡献值（当前节点+max(左贡献,右贡献)）

剩余步骤：14

思考 第8步 检查:

边界情况检查：

1. 空节点返回0
2. 叶子节点只返回自身值
3. 负数贡献值应该被舍弃（取0）
4. 考虑只有一个节点的情况

剩余步骤：13

反思

算法的时间复杂度是O(N)，空间复杂度是O(H)，其中N是节点数，H是树的高度。这是最优解法。

评分

0.90

思考 第9步 总结:

这是一个典型的需要后序遍历的二叉树问题，核心是理解每个节点在路径中可以扮演的两种角色：

1. 作为路径的一部分向上提供贡献
2. 作为路径的转折点连接左右子树

最终答案

根据以上分析，我们可以得出如下结论：

1. 关键点1是：需要使用后序遍历，对每个节点分别计算其作为路径端点和作为连接点两种情况。
2. 关键点2是：使用全局变量记录最大路径和，在遍历过程中不断更新。
3. 总结：可以通过一个递归函数解决，该函数返回节点的最大贡献值，同时维护全局最大值。递归过程中需要特别处理负数贡献值，将其剪枝为0。时间复杂度O(N)，空间复杂度O(H)。

代码框架应该是：

def maxPathSum(root):
    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

思考 第1步 分析:

需要编写Python3代码实现二叉树最大路径和的解决方案。需要定义树节点结构和主要算法。

思考 第2步 提取信息:

1. 需要定义TreeNode类
2. 需要实现maxPathSum函数
3. 需要使用递归方法
4. 需要处理全局最大值

剩余步骤：19

思考 第3步 明确目标:

编写清晰、高效的Python代码，包含完整的类定义和解决方案。

剩余步骤：18

思考 第4步 开始推理:

先实现基础结构，然后添加核心算法。

最终答案

# 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: TreeNode) -> int:
            # 如果节点为空，返回0
            if not node:
                return 0
            
            # 递归计算左右子树的最大贡献值
            # 如果子树的贡献值为负，则取0
            left_gain = max(max_gain(node.left), 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

代码说明：

1. 定义了TreeNode类作为二叉树节点的数据结构
2. Solution类中实现了maxPathSum方法
3. 使用了一个内部函数max_gain来进行递归计算
4. 使用self.max_sum维护全局最大路径和
5. 对于每个节点：
   • 计算左右子树的最大贡献值
   • 计算以当前节点为转折点的路径和
   • 更新全局最大值
   • 返回节点对其父节点的贡献值

时间复杂度：O(N)，其中N是二叉树中的节点数
空间复杂度：O(H)，其中H是二叉树的高度，主要是递归调用栈的开销

这个解决方案可以处理所有测试用例，包括：

• 示例1：[1,2,3] -> 6
• 示例2：[-10,9,20,null,null,15,7] -> 42
• 特殊情况：单个节点、负值节点、空树等