Meta 二叉树最大路径和：可延伸收益与两侧候选

题目重点：在任意起终点的非空简单路径上求最大节点值和，处理负数与不经过根的答案。

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

路径非空且每节点最多一次，可起止任意节点。值可负；空树返回None，不把空路径0当答案。
输入普通二叉树，不要求BST。示例只返回和，路径输出是扩展。

解题路线

后序gain[node]表示必须含node且可向父继续接的最大单支和：node.val+max(0,leftGain,rightGain)。
穿node的完整候选可以选左右各一支：node.val+max(0,leftGain)+max(0,rightGain)。拿此候选更新全局最大，但只能向父返回单支gain，否则路径会在node处分叉。
best从第一个真实节点候选初始化，避免全负树错返回0。迭代postorder按id保存gain，节点是否可hash不影响。

手动走一遍

根−10，左9，右20且20下有15/7，最佳15→20→7合42，不经过根。[-3,−2]只选−2最佳，不允许返回空路径0。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def maximum_path_sum(root):
    """Nonempty path may start/end anywhere; empty tree returns None."""
    if root is None:return None
    gains={};answer=None;stack=[(root,False)]
    while stack:
        node,done=stack.pop()
        if not done:
            stack.append((node,True))
            if node.right is not None:stack.append((node.right,False))
            if node.left is not None:stack.append((node.left,False))
        else:
            left=max(0,gains.get(id(node.left),0));right=max(0,gains.get(id(node.right),0))
            through=node.val+left+right
            answer=through if answer is None else max(answer,through)
            gains[id(node)]=node.val+max(left,right)
    return answer

复杂度

O(n)时间、示例O(n)gain与栈；递归实现调用栈O(h)。大整数的求和成本随数值bit长度变化。

易错点与追问

容易失分的边界

把左右收益同时返回父节点会构成分叉而非简单路径。
将所有负节点丢弃可能丢掉连接两个高值子树必要的桥，候选仍必须包含转折节点的值。

继续深挖

若必须root到leaf，不能对负分支随意归零，要沿至少一条到叶路径结束。
恢复见证路径时记录gain所选child以及best转折点，负分支被截断的边界需保留。