LC124 二叉树中的最大路径和 · 逐题动画 · RuntimeScope

当前：LC124 · 二叉树中的最大路径和 · 首次出现于 Day 22 · 路径：顶栏「56天打卡」→ 点击 LC 题号 → 逐题动画

LC124 · 二叉树最大路径和 · 工程执行实验室

后序 DFS · global 拐点更新 · return 单边上报

求任意非空路径的最大和。路径可以不经过 root，也不要求到 leaf；节点不重复、路径不分叉。核心：global 在拐点处可接左右两边，return 给父节点只能选一边。

最优路径 15 → 20 → 7 · 和 = 42

不经过 root · 在子树内拐弯

核心 · global 拐点 vs return 单边

在二叉树中寻找任意非空路径的最大路径和。路径可以不经过 root，也不要求到 leaf，但节点不能重复，路径不能分叉。

· 最大路径不一定经过 root——最优解可能在子树内部拐弯。
· leftGain = max(0, dfs(left))：负贡献子树直接剪掉，等价于不选这条边。
· global 更新用 node.val + leftGain + rightGain：当前节点是路径最高拐点，左右都可接。
· return node.val + max(leftGain, rightGain)：给父节点只能返回单边向下链，不能带分叉。

dfs 五步骤

root == nil → return 0
leftGain = max(0, dfs(left))
rightGain = max(0, dfs(right))
global = max(global, val+L+R)
return val + max(L, R)

更新全局答案：左右都可接

global = max(global, node.val + leftGain + rightGain)

当前节点是路径最高拐点，左右子树的最优链可同时接入。

返回父节点：只能选一边

return node.val + max(leftGain, rightGain)

父节点只能继续接一条向下链，不能带分叉路径。

后序遍历：先收子树，再更新 global，最后 return

1.leftGain = max(0, dfs(left))，rightGain = max(0, dfs(right))，负贡献剪为 0。
2.global = max(global, node.val + leftGain + rightGain) — 拐点可接左右。
3.return node.val + max(leftGain, rightGain) — 只上报单边给父节点。

1/11 · 题目定义

11 步分镜：

Step 1题目定义

题目：任意非空路径的最大和，答案 42

给定二叉树 [-10, 9, 20, null, null, 15, 7]，求任意非空路径的最大路径和。路径可以不经过 root，也不要求到 leaf；节点不能重复，路径不能分叉。最优路径 15 → 20 → 7，和为 42——完全在右子树内部，不经过 -10。

在二叉树中寻找任意非空路径的最大路径和。路径可以不经过 root，也不要求到 leaf，但节点不能重复，路径不能分叉。
最大路径不一定经过 root——最优解可能在子树内部拐弯。
leftGain = max(0, dfs(left))：负贡献子树直接剪掉，等价于不选这条边。
global 更新用 node.val + leftGain + rightGain：当前节点是路径最高拐点，左右都可接。
return node.val + max(leftGain, rightGain)：给父节点只能返回单边向下链，不能带分叉。

为什么正确

在二叉树中寻找任意非空路径的最大路径和。路径可以不经过 root，也不要求到 leaf，但节点不能重复，路径不能分叉。

状态表 · 当前发生了什么

当前节点	global	return	机器状态
—	−∞	—	读题任意路径 · 可拐弯 · 不必过 root

调用栈

[]

最大路径和实验室·绿线 = 最优路径 15→20→7·红虚线 = 负贡献剪枝

递归栈 · 后序调用链

（空栈 · 尚未进入 dfs）

Go · maxPathSum

1func maxPathSum(root *TreeNode) int {
2    var global int
3    var dfs func(*TreeNode) int
4    dfs = func(node *TreeNode) int {
5        if node == nil { return 0 }
7        leftGain := max(0, dfs(node.Left))
8        rightGain := max(0, dfs(node.Right))
10        global = max(global, node.Val+leftGain+rightGain)
12        return node.Val + max(leftGain, rightGain)
13    }
14    dfs(root)
15    return global
16}

复杂度

时间: O(n)
空间: O(h)

每个节点访问一次，后序 DFS 线性扫描全树。

h 为树高。递归调用栈深度等于树高：平衡树约 O(log n)，最坏单链退化 O(n)。不是 O(1) · 平衡树 O(log n) · 最坏 O(n)

面试回答

后序 DFS。对每个节点：leftGain = max(0, dfs(left))，rightGain = max(0, dfs(right))；用 node.val + leftGain + rightGain 更新全局 max（当前节点作路径拐点，左右都可接）；向父节点返回 node.val + max(leftGain, rightGain)（只能延伸一条向下链）。空节点返回 0。时间 O(n)；空间 O(h)，最坏 O(n)，不是 O(1)。

常见错误

错误 1：把 LC112 的 root→leaf 模型搬过来

LC124 不要求 root→leaf，也不要求经过 root。最优路径 15→20→7 完全在右子树内部。

错误 2：return 值和 global 混为一谈

global 可以在拐点处接左右两边；return 给父节点只能选一边，否则父节点无法继续向上延伸成单链。

错误 3：忘记 max(0, gain) 剪负贡献

子树返回负值时不应接入当前路径，必须 max(0, dfs(child))，否则会把总和拉低。

错误 4：空间复杂度误写成 O(1)

递归 DFS 需要系统调用栈保存每层暂停状态，空间是 O(h)，最坏单链 O(n)，不是 O(1)。

页面总结

LC124 的核心不是 root→leaf 求和，而是三件事：

1. 最大路径可在子树内拐弯，不必经过 root（答案 42 在 15→20→7）
2. global 在拐点处接左右两边；return 给父节点只报单边链
3. max(0, gain) 剪掉负贡献，避免拉低路径和

迁移练习

LC543 · 二叉树的直径

同样 global 记录跨左右的最优值，return 给父节点只报单边深度。

LC687 · 最长同值路径

global vs return 双语义，在拐点处合并左右，向上只延伸同值链。

LC112 · 路径总和 I

LC112 是 root→leaf + remain 扣减；LC124 是任意路径 + 后序汇报，模型完全不同。