LeetCode 124 二叉树最大路径和 | 思路与实现

题目：给定二叉树，路径定义为从某个节点出发，经父子边到达任意节点（可只包含单个节点），路径不要求过根且不能重复节点。求所有路径中结点值之和的最大值。

核心思路

1. 后序 DFS：对每个节点，计算“能够向上贡献”的单边最大路径和 gain(node)；同时尝试以该节点为拐点的“穿过路径”left_gain + node.val + right_gain 更新全局答案。
2. 负贡献截断：单边向上贡献只取 max(0, 子树 gain)。
3. 答案更新：全局最大 ans = max(ans, left_gain + node.val + right_gain)。

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

def maxPathSum(root: TreeNode) -> int:
    ans = float("-inf")

    def gain(node: TreeNode) -> int:
        nonlocal ans
        if not node:
            return 0
        # 子树单边贡献（负则置0）
        left = max(0, gain(node.left))
        right = max(0, gain(node.right))
        # 以当前节点为拐点的“穿过路径”
        ans = max(ans, left + node.val + right)
        # 返回能向父节点继续延伸的单边最大贡献
        return node.val + max(left, right)

    gain(root)
    return ans
            

常见坑

• 允许路径只有单个节点，因此初始 ans 不能是 0，应为 -inf。
• 不要把“单边”与“穿过”混淆：返回给父亲的是单边，更新全局的是穿过。
• 节点值可能为负，记得对左右子树贡献取 max(0, ...)。

复杂度

每个节点访问一次：时间 O(N)，额外递归栈空间 O(H)。