LeetCode 124. 二叉树中的最大路径和
目录
题目描述
题意分析
题目要求在一棵二叉树中找出「最大路径和」。这里「路径」的定义很特殊：从树中任意节点出发、到任意节点结束，沿父子边行走且每个节点最多出现一次；它不必经过根节点，也不必从叶子开始或结束，甚至可以只包含一个节点——但至少要包含一个节点，不存在「空路径记 0 分」的说法。
节点值的范围是
[-1000, 1000]，可能为负，这个信号非常重要：接上一段子路径可能反而拉低总和，所以「多接多得」的直觉不成立；而当整棵树全是负数时，答案就是「值最大的那个单节点」，仍然是负数。节点数最多 $3 \times 10^4$，且路径两端可以是任意两个节点，如果逐一枚举端点组合再求和，规模上明显吃不消，题目实际期望每个节点只被处理常数次。边界上注意树保证非空，单节点树的答案就是该节点值本身。
解法：后序 DFS 计算单边贡献
核心思路
后序 DFS 返回“从当前节点出发、向下选择一侧”的最大贡献，供父节点继续连接。当前节点作为路径最高点时可以同时连接左右贡献，用
node.val + left + right更新全局答案；负贡献直接舍弃。
解题步骤
- 空节点返回
0，表示不连接该侧。- 后序计算左右子树贡献，并用
max(0, gain)舍弃负贡献。- 用“左贡献 + 当前值 + 右贡献”更新最大路径和。
- 向父节点只返回“当前值 + 较大的一侧贡献”。
代码实现
class Solution {
private int best;
public int maxPathSum(TreeNode root) {
best = root.val;
gain(root);
return best;
}
private int gain(TreeNode node) {
if (node == null) {
return 0;
}
int left = Math.max(0, gain(node.left));
int right = Math.max(0, gain(node.right));
best = Math.max(best, node.val + left + right);
return node.val + Math.max(left, right);
}
}
func maxPathSum(root *TreeNode) int {
best := root.Val
var gain func(*TreeNode) int
gain = func(node *TreeNode) int {
if node == nil {
return 0
}
left, right := gain(node.Left), gain(node.Right)
if left < 0 {
left = 0
}
if right < 0 {
right = 0
}
if sum := node.Val + left + right; sum > best {
best = sum
}
if right > left {
left = right
}
return node.Val + left
}
gain(root)
return best
}
复杂度分析
- 时间复杂度：$O(n)$，每个节点访问一次。
- 空间复杂度：$O(h)$，
h为树高，来自递归栈。
关键点总结
- 返回值是可向父节点延伸的单边路径，不能同时包含左右子树。
- 全局答案统计以当前节点为最高点的完整路径，可以同时连接两侧。
- 舍弃负贡献，但不能舍弃当前节点本身。
易错点总结
- 最大值不能初始化为
0，否则全负树会得到不存在的空路径。- 把左右贡献之和向上返回会形成分叉，不再是一条合法路径。
- 只返回根节点的单边贡献，会漏掉不经过根节点的最优路径。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 543. 二叉树的直径 | 简单 | 同款「返回单链、答案取双链」模板，统计量换成边数且无负值 |
| 687. 最长同值路径 | 中等 | 在模板上叠加「父子同值才允许延伸」的链条断裂判断 |
| 437. 路径总和 III | 中等 | 只统计单向向下的路径条数，用前缀和哈希替代拐点枚举 |
| LCR 051. 二叉树中的最大路径和 | 困难 | 本题的镜像题，可用来自测同一套贡献值模板 |