【LC 124】二叉树中的最大路径和：返回值为什么只能选一条胳膊
适用读者：会写二叉树的后序递归，但一看到「返回值」和「答案」要同时维护就觉得别扭的人
技术栈：Python 为主，附 Java 版
难度：困难（代码 10 行，但这 10 行里藏着一个真正的思维跳跃）
收获：一个「一个节点同时算两个量」的树形 DP 模板，以及 543 / 687 / 1123 一整串同骨架的变体
题目
路径被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中
至多出现一次。该路径
至少包含一个节点，且
不一定经过根节点。
路径和是路径中各节点值的总和。给你一个二叉树的根节点
root，返回其
最大路径和。
输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 → 20 → 7，路径和为 15 + 20 + 7 = 42
输入：root = [1,2,3]
输出：6
解释：最优路径是 2 → 1 → 3
输入：root = [-3]
输出：-3
这题是
树形 DP 的分水岭。它不是那种"多写几个 if 就能过"的题 —— 它要求你想明白一件事：
变体也成串 —— 它们
共用同一个骨架，只换掉"两个量"的定义：
出处备注：LC 124 是字节、腾讯、阿里的树形 DP 高频题。被选中的原因很直接：代码只有 10 行，但"为什么返回值只能选一条胳膊"说不清楚的人占大多数。 面试官最爱的追问就是"返回值为什么不写成 val + left + right？"—— 本文第 1.3 节专门回答它。
节点的定义，沿用前几篇：
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
输入格式提醒：[-10,9,20,null,null,15,7] 是 LeetCode 的层序数组编码（和 LC 102 / LC 236 一样）。下标 i 的节点，左孩子在 2i+1、右孩子在 2i+2，空缺位置用 null 占位。这棵树画出来是：
-10
/ \
9 20
/ \
15 7
9 的两个孩子位是 null（它是叶子），所以 [15, 7] 挂在 20 下面。整棵树只有 5 个节点。
一、先说清楚这题到底难在哪
1.1 直觉方案为什么不够好
最直白的想法是：
枚举所有路径，取最大的那个。
def maxPathSum(self, root):
best = -float('inf')
def all_paths_from(node): # 以 node 为一端的、向下的所有直链
if not node:
return [0]
lefts = all_paths_from(node.left)
rights = all_paths_from(node.right)
return [node.val + x for x in lefts] + [node.val + x for x in rights]
def dfs(node): # 枚举以 node 为"最高点"的所有路径
nonlocal best
if not node:
return
for a in [0] + all_paths_from(node.left):
for b in [0] + all_paths_from(node.right):
best = max(best, node.val + a + b)
dfs(node.left)
dfs(node.right)
dfs(root)
return best
这个写法
是对的，但复杂度难看：
all_paths_from 会重复遍历子树，整体退化到 O(n²) 甚至更高。n = 3×10⁴ 的时候会超时。
问题出在哪？
它把每棵子树算了无数遍。 而真正需要的信息，其实只有一个数 —— 这就是后序 DP 能进来的地方。
1.2 关键观察：一条路径在树上长什么样
先看清楚"路径"这个形状。因为
同一个节点至多出现一次，一条路径在二叉树上的形状只有两种：
① 直链（一条胳膊） ② 拱形（两条胳膊）
● ← 最高点
● / \
| ● ●
● | |
| ● ●
●
（深度最小的那个，也就是拐弯的地方）。
- 如果路径是直链，最高点就是它的上端点，只有一条"胳膊"往下走；
- 如果路径是拱形，最高点就是那个拐弯处，有两条胳膊，一条往左、一条往右。
有了这个观察，整个问题就变成了：
对每个节点，算出「以它为最高点的最优路径」，再取所有节点的最大值。
而"以
node 为最高点的最优路径"可以拆成三块：
node.val + (左子树里最优的那条向下直链) + (右子树里最优的那条向下直链)
这是个极其容易搞混的地方：子树里最优的那条路径可能是拱形的（比如
15 → 20 → 7 就在
20 这棵子树里，它是个拱），但你
没法把一条拱形路径接到父节点上去 —— 接上去就变成树杈了。
接得上去的，只能是
从子树根一路往下走的直链。所以我们真正需要从子树拿到的，是这个东西：
def gain(node): # 从 node 出发、一路向下的所有直链里，最大的那条的"和"
if not node:
return 0
return node.val + max(gain(node.left), gain(node.right))
这就能在 O(n) 里自底向上算出来。
gain 就是「贡献值」 —— 这棵子树愿意往上贡献多少。
1.3 本题唯一真正的难点：两个量必须分开算
现在把两件事拼起来，你会发现一个节点要同时算
两个不同的东西：
def gain(node):
if not node:
return 0
left = max(gain(node.left), 0) # ← clamp：负贡献直接剪掉
right = max(gain(node.right), 0)
# ① 以 node 为「拱顶」的完整路径（两条胳膊都用上，用到此为止）
best = max(best, node.val + left + right)
# ② 向上汇报的「贡献值」（只能选一条胳膊）
return node.val + max(left, right)
val + left + right？
答案是：
路径不能拐两次弯。
想象一下，如果
20 返回
20 + 15 + 7 = 42（两条胳膊都用掉）。父节点
-10 拿到 42，它自己也想拐一次弯接上去，于是算
-10 + 42 = 32 —— 但
15 → 20 → 7 这条路径上，
20 已经拐过一次弯了。在
20 那里再往上接到
-10，就变成了：
这是
一个分叉的树杈，不是一条路径 —— 因为
20 在这一条路径里出现了两次（一次作为通往 15 的中转，一次作为通往 7 的中转），违反了"至多出现一次"。
✗ 拐两次（不是路径） ✓ 只拐一次（是路径）
-10 -10
/ /
20 20
/ \ /
15 7 7
所以：
向上汇报时必须"留一手"，只带一条胳膊走。而
through 之所以能两条胳膊都用，是因为
它就在本节点处结束，不再往上接了 —— 不需要留手。
一句话记法：
返回一条边，答案一个尖。
1.4 max(gain, 0) 里的那个 0，就是本题的优化本身
很多人会把
max(gain(node.left), 0) 当成"防御性编程"（"万一子树是 null 呢"）。
不是的。
那个
0 表达的是一个
决策：
如果一条胳膊的总和是负的，把它接进来只会让路径和变小，那不如不接。
- 不剪枝：
through = 1 + (-5) + 3 = -1
- 剪枝后：
through = 1 + 0 + 3 = 4 ← 正确
gain(-5) = -5，
max(-5, 0) = 0，含义是
"别走我这边，从 1 直接往右拐到 3 就好"。
所以代码里的
max(·, 0) 不是可选的保险，它和
best 的更新是
同等重要的两半。去掉它，这题就错了。
1.5 best 为什么必须初始化成 -Infinity
题目说"路径
至少包含一个节点"。如果
best 初始化成
0：
输入：root = [-3]
输出：0 ← 错！0 对应"空路径"，但空路径不是合法路径
正确答案：-3
全负的树是最容易暴露这个 bug 的用例。
best 要初始化成 -float('inf')，保证至少有一个节点会被算进去。
二、动画：看着贡献值一层层往上冒
下面这个动画把上面 13 帧推演过程逐帧画出来。图里：
- 每个节点上方挂的
gain 标签 = 它向上汇报的贡献值（"冒泡"上来的那个数）；
- 金色细圈 = 当前最优路径上的节点；金色粗圈 = 这条路径的拱顶（最高点）；
- 虚线圆圈 / 虚线边 = 贡献值 ≤ 0、被
max(·, 0) 剪掉的胳膊；
- 下面那条横幅 = 当前全局最优的
best 和它对应的完整路径。
看的时候重点盯三处：
- 第 3 帧，
9 报出 gain 9，best 从 -Infinity 变成 9；
- 第 9 帧，
20 拿到左右各 15 和 7，算出的 through = 42 直接刷新 best，同时只报出 gain 35（不是 42）—— 这就是"留一手"；
- 第 12 帧（终帧），看根
-10 的 through = 34：它比 42 小，所以根不是答案。这正说明题目那句"路径不一定经过根节点"。
三、完整推演表（13 帧逐帧）
下面是动画每一帧的真实数据（
L /
R 是 clamp
之后的左右贡献值；
through 是拱顶路径和，
gain 是向上汇报的贡献值）：
两行必须对照着看：
第 9 帧（20） —— 这就是本题的全部难点：
L = 15, R = 7
through = 20 + 15 + 7 = 42 ← 两条胳膊都用，更新 best（42 > 15，刷新！）
gain = 20 + max(15, 7) = 35 ← 只选一条胳膊，交给父节点
through 和
gain 差了整整 7 —— 那个 7 就是"被留下没带走"的右胳膊。
第 11 帧（-10） —— 为什么根不是答案：
L = 9, R = 35 ← 右孩子 20 报上来的 gain 是 35，不是 42！
through = -10 + 9 + 35 = 34 ← 34 < 42，所以 best 保持 42 不动
gain = -10 + max(9, 35) = 25
如果第 9 帧
20 错误地报了
42，那么这里就会算成
-10 + 9 + 42 = 41 —— 依然小于 42，这一例
看起来还是对的。但换个树就会崩。这就是为什么"两个量分开算"不能靠"跑通样例"来验证，
必须从原理上理解。
你可以自己构造一个反例感受一下：[1, 2, 3, 4, 5] 这种对称树，如果返回值错误地带上两条胳膊，根的 through 会严重虚高（把子树的拱形路径重复计入），答案会明显偏大。
第 12 帧收尾时，栈已清空，
best = 42，
bestPath = [15, 20, 7] —— 注意
它完全不经过根 -10。
四、完整代码
4.1 Python 版（10 行主逻辑）
class Solution:
def maxPathSum(self, root: TreeNode) -> int:
self.best = -float('inf') # ← 不能是 0：路径至少含一个节点
def gain(node: TreeNode) -> int:
"""返回 node 向上汇报的贡献值（一条胳膊的直链最大和）。"""
if not node:
return 0
left = max(gain(node.left), 0) # ← 负贡献直接剪掉
right = max(gain(node.right), 0)
# ① 以 node 为拱顶的完整路径（两条胳膊），用它更新全局最优
self.best = max(self.best, node.val + left + right)
# ② 向上汇报的贡献值（只能选一条胳膊）
return node.val + max(left, right)
gain(root)
return self.best
4.2 逐行拆解
self.best = -float('inf')
：见 1.5。全负树会被这个细节一刀毙命。
left = max(gain(node.left), 0)
right = max(gain(node.right), 0)
两个
0 就是
剪枝决策（见 1.4）。注意这里
gain(node.left) 会自动处理
None 的情况（第一行
if not node: return 0），所以不用额外判空。
self.best = max(self.best, node.val + left + right)
：拱顶路径，两条胳膊都用。它
不返回值，只更新答案。这是"到此为止"的那条路径。
return node.val + max(left, right)
：向上贡献，只能选一条胳膊。
max(left, right) 就是"选更粗的那条胳膊"。
顺序很重要：必须先更新
best 再
return，因为
through 是"到此为止"的量，一旦返回就丢掉了。
4.3 复杂度
对比 1.1 节的暴力枚举（O(n²) 以上），这就是后序 DP 的价值。
五、变体一：LC 543 二叉树的直径
5.1 只换掉"量"的定义
LC 543 二叉树的直径：给你一棵二叉树的根节点，返回该树的
直径 —— 任意两个节点之间最长路径的
边数。
同一个骨架，只把两个量换掉：
5.2 代码
class Solution:
def diameterOfBinaryTree(self, root: TreeNode) -> int:
self.best = 0 # ← 这次可以是 0：直径最小就是 0（单节点）
def depth(node: TreeNode) -> int:
if not node:
return 0
left = depth(node.left) # ← 不需要 clamp，深度天然 >= 0
right = depth(node.right)
self.best = max(self.best, left + right) # ① 拱顶处：两条胳膊长度相加
return 1 + max(left, right) # ② 向上：只带最长的一条
depth(root)
return self.best
5.3 两者的对照
注意 LC 543 里没有 max(·, 0) —— 因为深度不可能为负，那个 clamp 在这里毫无意义。这恰好反证了：
LC 124 里那个 0 是为了"值可为负"这个前提服务的，不是通用写法。
另外
best 的初值也不同：124 必须
-inf（路径至少一个节点，值可能全负），543 可以用
0（直径最小就是 0）。
面试小技巧：如果面试官先给你 124 再给你 543，你可以主动说"这是同一个骨架，只是把节点值换成了边数"，然后指出"543 不需要 clamp" —— 这句话能直接证明你是理解了而不是背过了。
六、变体二：LC 687 最长同值路径
6.1 再加一层约束
LC 687 最长同值路径：返回树中最长同值路径的
边数（路径上每个节点值都相同）。
还是同一个骨架，但在"选哪条胳膊"时多加一个条件：
孩子的值必须等于自己的值。
6.2 代码
class Solution:
def longestUnivaluePath(self, root: TreeNode) -> int:
self.best = 0
def arrow(node: TreeNode) -> int:
"""node 向上汇报的、以 node 为起点且值全同的向下链长度（边数）。"""
if not node:
return 0
l = arrow(node.left)
r = arrow(node.right)
# 关键差异：孩子值不等于自己 → 这条胳膊断掉，长度归 0
left = l + 1 if node.left and node.left.val == node.val else 0
right = r + 1 if node.right and node.right.val == node.val else 0
self.best = max(self.best, left + right) # ① 拱顶：两条胳膊
return max(left, right) # ② 向上：一条胳膊
arrow(root)
return self.best
6.3 骨架三兄弟对照
三题共用同一个 10 行骨架。
掌握了 124，另外两题就是改两行。
七、再顺手带两个
7.1 LC 变体：最大路径乘「乘积」
如果题目把"和"换成"乘积"，会发生一件危险的事：
不能盲目 clamp。
-5 × -3 = 15（负负得正），所以一个"负的胳膊"接进来反而可能让乘积变大。这时必须同时维护
最大值和最小值两个返回值：
def gain(node):
if not node:
return (1, 1) # (最大, 最小)
lmax, lmin = gain(node.left)
rmax, rmin = gain(node.right)
# 四个候选：自己的值、自己×左最大、自己×左最小、…… 全排列出极值
cands = [node.val, node.val * lmax, node.val * lmin,
node.val * rmax, node.val * rmin]
self.best = max(self.best, max(a * b for a in cands for b in cands))
return (max(cands), min(cands))
：
max(·, 0) 的 0 是针对"加法"这个运算的
下界。换运算就得重新推理下界是什么 —— 别把模板当教条。
7.2 LC 1123 最深叶节点的最近公共祖先
这题也用同一套"拱顶"思路，只是两个量的含义换成
高度：
def dfs(node):
if not node:
return (0, None) # (子树高度, 子树内最深叶的 LCA)
ld, llca = dfs(node.left)
rd, rlca = dfs(node.right)
if ld == rd:
return (ld + 1, node) # 左右一样深 → 自己就是 LCA（拱顶）
if ld > rd:
return (ld + 1, llca) # 只带更深的那条（一条胳膊）
return (rd + 1, rlca)
看到没有 ——
if ld == rd: 自己是拱顶 / else: 带走更深的那条，和 124 的
through /
gain 是
完全同构的。
八、Java 版
class Solution {
private int best = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
gain(root);
return best;
}
private int gain(TreeNode node) {
if (node == null) return 0;
int left = Math.max(gain(node.left), 0);
int right = Math.max(gain(node.right), 0);
// ① 拱顶路径：两条胳膊都用
best = Math.max(best, node.val + left + right);
// ② 向上贡献：只选一条胳膊
return node.val + Math.max(left, right);
}
}
：
Integer.MIN_VALUE 在极端情况下可能溢出。如果题目允许路径和接近
-2^31，建议用
long best 或者初始化为
-Integer.MAX_VALUE。LeetCode 124 的数据范围（
-1000 <= val <= 1000，节点数 ≤ 3×10⁴）下
Integer.MIN_VALUE 是安全的，但面试时提一句会加分。
九、边界情况
最容易错的三个：
[-3] → 错答 0（best 初值错）[-1,-2,-3] → 错答 0 或 -2（前者初值错，后者忘了"至少一个节点"）[1,-2,3] → 错答 2（忘了 max(·, 0) 剪枝，算成 1 + (-2) + 3）
十、常见坑
坑 1：返回值写成 val + left + right
最经典的错误。表面上跑样例
[-10,9,20,null,null,15,7] 还能得 42（因为根是负数，虚高的值恰好没被选中），但换棵树就崩。
判断方法：在心里画一棵对称树
[1,2,3]。正确
gain(1) = 1 + max(2,3) = 4；错误写法
gain(1) = 1 + 2 + 3 = 6。父节点如果存在，拿到 6 就会算出离谱的值。
坑 2：best 初始化成 0
全负树上必错。
记法：题目说"至少包含一个节点"，那答案就不可能是"空路径"的 0。
坑 3：把 max(·, 0) 当成防御性编程
它不是。
去掉它，[1,-2,3] 会从 4 变成 2。 见 1.4。
坑 4：先 return 再更新 best
return node.val + max(left, right) # ← 提前返回了
self.best = max(...) # ← 永远执行不到
through 是"到手即用"的量，必须在函数结束前用掉。
坑 5：None 的 gain 返回什么
if not node: return 0 —— 返回
0 而不是 -inf。因为空子树"不贡献也不拖累"，
max(0, 0) = 0 正好对应"不走这边"。
十一、面试怎么答
第一步：先定义清楚两个量（这是得分点）
"这题的关键是每个节点要同时算两个不同的量。一个是以自己为最高点的完整路径和，用两条胳膊，它只用来更新全局答案；另一个是向上汇报的贡献值，只能带一条胳膊走。"
第二步：主动解释"为什么只能带一条胳膊"（这是加分点）
"因为路径不能拐两次弯。父节点拿到返回值后还会再拐一次，如果这里两条胳膊都用掉，父节点再拐就变成树杈了，不是路径。"
第三步：主动提 max(·, 0) 的语义
"这里的 max(gain, 0) 不是判空，是个剪枝决策 —— 负的胳膊接进来只会让和更小，所以返回 0 表示'别走我这边'。"
第四步：主动提 -inf
"best 要初始化成负无穷，因为题目保证路径至少含一个节点、值可以是负数。用 0 的话 [-3] 会错答 0。"
第五步：报复杂度 + 挂钩变体
"时间 O(n)，空间 O(h)。这题和 LC 543 二叉树的直径是同一个骨架，只是把节点值换成边数、并且 543 不需要 clamp。"
如果被追问「能不能不用全局变量？」 —— 可以把
best 装进一个单元素列表或者用返回值
(gain, best) 元组带上：
def gain(node):
if not node:
return 0, -float('inf')
l, lb = gain(node.left)
r, rb = gain(node.right)
l, r = max(l, 0), max(r, 0)
return node.val + max(l, r), max(lb, rb, node.val + l + r)
—— 会。偏斜树有 3×10⁴ 个节点时，Python 默认递归深度 1000 会
RecursionError。两个办法：把递归上限调高（
sys.setrecursionlimit(1000000)），或者手写显式栈（本文的动画状态机用的就是显式栈，栈帧
{id, stage, from} 配合
stage 机推进，思路和 LC 236 那篇一样）。
结语
LC 124 只有 10 行，但它逼你想清楚一件在别的题里很少被逼着面对的事：
同一个节点，向上汇报和更新答案，可以是两个不同的值。
理解了这一点，
max(·, 0) 就不再是"顺手写的保险"，
-inf 也不再是"随手写的初值" —— 它们都是这道题的
逻辑本身。
而这一套「一个节点两个量」的骨架，能一路打通
543 / 687 / 1123，甚至换成乘法的变体。下次再看到"树上最长路径"类的题，先问自己两个问题：
- 向上汇报的那个量，是什么？（一条胳膊）
- 更新答案的那个量，是什么？（两条胳膊）
回答完这两句，代码基本就出来了。
系列导航：本文是「暑期面经汇总」算法系列的第 12 篇。前作：LC 206 反转链表 · LC 21 合并两个有序链表 · LC 23 合并 K 个升序链表 · LC 141/142 环形链表 · LC 19 删除链表倒数第 N 个节点 · LC 143 重排链表 · LC 234 回文链表 · LC 160 相交链表 · LC 82 删除排序链表中的重复元素 II · LC 102 二叉树的层序遍历 · LC 236 二叉树的最近公共祖先。