124. 二叉树中的最大路径和 (Hard)
专题归类： 05-二叉树 LeetCode 链接： https://leetcode.cn/problems/binary-tree-maximum-path-sum/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 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 * 10^4] -1000 <= Node.val <= 1000
题目详细分析
- 数据范围含义： 最多 30000 个节点，值范围 [-1000, 1000]，递归深度最坏 30000，Python 递归可能栈溢出。需要考虑迭代法或设置 recursionlimit。
- 输入输出特征： 输入根节点，输出最大路径和（整数）。
- 边界条件： 只有一个节点时返回该节点值（即使为负）。节点值可能为负，最大路径和也可能是负数。
- 核心约束： 路径可以拐弯——即从某个节点的左子树上来，经过该节点，再下到右子树。但不能有分叉（不能同时走左右子树后再往上走）。路径至少包含一个节点。
- 隐藏条件： 路径可以不完全经过根节点，所以必须全局搜索。这与「二叉树的直径」（543）的思路几乎一致，但本题是节点值的和，并且负数贡献可以舍弃。
小白版直白理解
就像在树状的城市路网中找一条收益最高的送货路线——每个路口有收益（也可能是亏损），你可以从任何一个路口出发，在任何一个路口结束，但你不能走回头路。路线可以在某个路口拐弯（从左支路上来，经过路口，再去右支路），但不能分岔（不能同时去左右后再回来）。
关键策略：如果某条支路让你亏损（负收益），那就不走那条路——收益为 0。
解题思路
思路一：后序遍历 + 全局变量（推荐）
核心思想： 每个节点可以计算两个值：
- 经过当前节点的最大路径和 =
max(0, 左子树贡献) + node.val + max(0, 右子树贡献)。这是「拐弯」路径，用于更新全局最大值。 - 当前节点的单边最大贡献 =
node.val + max(max(0, 左子树贡献), max(0, 右子树贡献))。这是「不拐弯」的路径，向上返回给父节点使用。父节点只能选择一条子树路径来延伸。
为什么用后序？ 要计算「经过当前节点的路径和」，必须先知道左右子树的贡献值。这是典型的依赖子树信息的计算，必须用后序位置来操作。前序和中序都无法做到（进入节点时还不知道子树信息）。
def maxPathSum(root):
max_sum = float('-inf') # 全局最大路径和
def dfs(node):
nonlocal max_sum
if not node:
return 0
# 后序：先计算左右子树的最大贡献
# max(贡献, 0)：如果子树贡献为负，就舍弃（不走这条路）
left_gain = max(dfs(node.left), 0)
right_gain = max(dfs(node.right), 0)
# 经过当前节点的最大路径和（可以拐弯）
current_path_sum = left_gain + node.val + right_gain
# 更新全局最大值
max_sum = max(max_sum, current_path_sum)
# 返回当前节点的单边最大贡献（不能拐弯，供父节点使用）
return node.val + max(left_gain, right_gain)
dfs(root)
return max_sum思路二：转化为直径问题的变体
与 543-二叉树的直径 完全相同的结构。区别在于：
- 直径取的是左右深度之和（边数），最大路径和取的是
max(0, left) + val + max(0, right) - 直径计算深度时不需要考虑负数（深度非负），最大路径和需要通过
max(gain, 0)舍弃负贡献
def maxPathSum(root):
max_sum = float('-inf')
def max_gain(node):
nonlocal max_sum
if not node:
return 0
left = max_gain(node.left)
right = max_gain(node.right)
# 左中右都取，组成完整路径（经过当前节点）
max_sum = max(max_sum, left + node.val + right)
# 向上只能返回单边最大值（加上当前节点）
# 如果左右都是负数，返回 node.val 本身
return node.val + max(left, right, 0)
max_gain(root)
return max_sum注意这个版本和思路一的区别：思路一中 max(dfs(node.left), 0) 在递归函数内部处理，而这里把截断逻辑放在了 max(left, right, 0) 中（向上返回时处理）。两种写法等价。
易错点
max_sum初始化为负无穷： 因为节点值可能全为负数，最大路径和可能是负数。如果初始化为 0，当所有路径和为负时会返回 0（错误）。必须用float('-inf')。- 舍弃负贡献：
max(dfs(node.left), 0)中的max(..., 0)是核心——如果子树的贡献是负数，就不走那一边。这是路径和问题与直径问题最大的区别（直径不需要截断，因为深度总是非负）。 - 返回值和全局变量的区别： 递归函数返回值是「单边最大贡献」（不能拐弯），全局变量
max_sum记录「经过某个节点的最大路径和」（可以拐弯）。两者含义完全不同，不能混淆。 - 路径至少包含一个节点： 即使所有节点值都是负数，也要选一个最大的负数作为结果，不能返回 0。所以
max_sum的初始值必须是负无穷，保证至少能取到一个节点的值。 - 空节点返回 0，不是返回负无穷： 空节点没有贡献，返回 0。如果把空节点返回负无穷，
max(负无穷, 0)会取 0，逻辑不对。
框架提炼
后序归并 + 全局变量模板（适用于树上的全局最优解问题）：
def tree_best(root):
best = float('-inf') # 全局最优解
def postorder(node):
nonlocal best
if not node:
return base_value
left = postorder(node.left)
right = postorder(node.right)
# 后序位置：用左右子树的结果更新全局最优
best = max(best, combine(node, left, right))
# 返回当前节点对上一层的贡献（单向，不可分叉）
return contribution(node, left, right)
postorder(root)
return best应用对比：
| 问题 | combine(node, L, R) | contribution(node, L, R) |
|---|---|---|
| 543-直径 | L_depth + R_depth | 1 + max(L_depth, R_depth) |
| 124-最大路径和 | max(0, L_gain) + val + max(0, R_gain) | val + max(0, L_gain, R_gain) |
| 968-监控二叉树 | 根据子节点状态的组合判断 | 返回当前节点的状态 |
关联题目
- 543-二叉树的直径 — 完全相同的「后序 + 全局变量」模式，是本题的简化版（边数 vs 节点值和，无负数问题）。
- 437-路径总和 III — 同样是路径统计问题，但 437 求的是特定和的出现次数（不能拐弯），而 124 求的是最大和（可以拐弯）。
- 236-二叉树的最近公共祖先 — 后序递归的经典应用，同样需要利用后序位置整合子树信息。