二叉树的最大路径和问题

题目描述
给定一个非空二叉树，每个节点有一个整数值，找到一条路径（从树中任意节点出发，到达任意节点，方向只能从上往下），使得路径上的节点值之和最大。返回这个最大值。路径至少包含一个节点，且不一定经过根节点。

解题思路分析
这个问题看似复杂，但可以通过分解为子问题来解决。关键点在于：

1. 路径可以是任意节点到任意节点的路径，不一定经过根节点
2. 路径方向必须是单向的（父节点→子节点）
3. 我们需要考虑三种情况：左子树路径、右子树路径、跨越根节点的路径

循序渐进讲解

步骤1：理解路径的三种可能情况
对于任意节点，经过该节点的最大路径和有三种可能：

• 情况1：只包含当前节点本身
• 情况2：当前节点 + 左子树的某条路径
• 情况3：当前节点 + 右子树的某条路径
• 情况4：当前节点 + 左子树路径 + 右子树路径（这种路径不能继续向上延伸）

步骤2：定义递归函数
我们定义一个递归函数 maxPathSumHelper(node)，它返回两个值：

1. 以该节点为起点的向下最大路径和（可用于父节点计算）
2. 经过该节点的最大路径和（可能是跨越左右子树的路径）

步骤3：递归处理子问题
对于每个节点：

• 如果节点为空，返回0（空节点不贡献值）
• 递归计算左子树和右子树的最大路径和
• 注意：如果子树的最大路径和为负数，我们宁愿不选择它（取0）

步骤4：计算当前节点的各种路径和

1. 以当前节点为起点的最大路径和 = max(0, 左子树最大路径和, 右子树最大路径和) + 节点值
2. 经过当前节点的最大路径和 = max(以当前节点为起点的最大路径和, 节点值 + 左子树最大路径和 + 右子树最大路径和)

步骤5：维护全局最大值
在递归过程中，我们需要维护一个全局变量来记录整个树中的最大路径和。

具体实现

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        self.max_sum = float('-inf')
        
        def dfs(node):
            if not node:
                return 0
            
            # 递归计算左右子树的最大贡献值
            left_max = max(dfs(node.left), 0)
            right_max = max(dfs(node.right), 0)
            
            # 计算经过当前节点的最大路径和
            current_max = node.val + left_max + right_max
            self.max_sum = max(self.max_sum, current_max)
            
            # 返回以当前节点为起点的最大路径和
            return node.val + max(left_max, right_max)
        
        dfs(root)
        return self.max_sum

步骤6：复杂度分析

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

关键要点总结

1. 使用后序遍历（左右根）来保证先处理子问题
2. 负贡献值要舍弃（取0）
3. 区分"以节点为起点的路径"和"经过节点的路径"
4. 使用全局变量记录最大值

这个问题的核心思想是将复杂问题分解为子问题，通过递归自底向上地解决，是二叉树问题中的经典范例。