二叉树中的最大路径和
Binary Tree Maximum Path Sum
本机进度仅保存在当前浏览器
题目描述
二叉树中的「路径」被定义为一条节点序列，序列中每对相邻节点之间都存在边，且每个节点至多出现一次；路径至少包含一个节点，不必经过根节点。路径和是路径中各节点值的总和。给你二叉树的根节点 root，返回其最大路径和（节点值可能为负）。
示例：[1, 2, 3] 输出 6（路径 2 -> 1 -> 3）；[-10, 9, 20, null, null, 15, 7] 输出 42（15 -> 20 -> 7）。
解题思路
- 区分两个量：「穿过当前节点的路径和」（左链 + 右链 + 自身，用于更新答案）与「向上贡献的链和」（自身 + 左右链中较大的一条，用于递归）。
- 链和若为负，贡献只会拖累父节点，取 max(链和, 0) 实现负值剪枝。
- 答案在递归过程中全局更新：ans = max(ans, left + right + val)；注意至少包含一个节点，负值也要正确处理。
参考实现
查看参考实现Python · 建议先自行作答
def maxPathSum(root):
best = float('-inf')
def gain(node):
# 返回以 node 为端点向下的最大链和（负贡献剪为 0）
nonlocal best
if not node:
return 0
left = max(gain(node.left), 0)
right = max(gain(node.right), 0)
best = max(best, node.val + left + right)
return node.val + max(left, right)
gain(root)
return best