二叉树的最大路径和
一句话说明
这题必须把“返回给父节点的贡献值”和“当前节点作为拐点时的完整路径值”拆开看，否则一定会写乱。
这题为什么容易卡住
很多人会误以为它求的是：
- 根到叶最大路径和
- 或者某条一直向下的单链最大和
都不对。
这题的路径可以：
- 从任意节点开始
- 到任意节点结束
- 但必须沿父子边连续走
所以路径不一定经过根，也不一定只能单向往下。
这题最关键的两个量
向上贡献值
gain(node) 表示：
如果这条路径还要继续接到父节点，
当前节点最多能提供多少价值？因为往上接时不能分叉，所以只能选左边或右边的一条链。
全局答案
answer 表示整棵树里见过的最大路径和。
它允许当前节点把左右两边都接上，把自己当拐点。
Go 代码：标准模板
func MaxPathSum(root *TreeNode) int {
answer := math.MinInt
var gain func(node *TreeNode) int
gain = func(node *TreeNode) int {
if node == nil {
return 0
}
leftGain := max(gain(node.Left), 0)
rightGain := max(gain(node.Right), 0)
currentPath := node.Val + leftGain + rightGain
answer = max(answer, currentPath)
return node.Val + max(leftGain, rightGain)
}
gain(root)
return answer
}
func max(a, b int) int {
if a > b {
return a
}
return b
}为什么负贡献直接按 0 处理
如果某个子树贡献是负数，接上它只会让路径更差。
而题目允许路径从任意节点开始，所以没必要硬把负数子树带上。
这就是：
leftGain := max(gain(node.Left), 0)
rightGain := max(gain(node.Right), 0)背后的真正原因。
一个例子走通
-10
/ \
9 20
/ \
15 7在节点 20：
- 左贡献
15 - 右贡献
7 - 当前完整路径
20 + 15 + 7 = 42
这会刷新全局答案。
但返回给父节点时，只能返回：
20 + max(15, 7) = 35因为往上只能接一条链。
为什么这是后序思路
因为当前节点必须先知道：
- 左子树给它多少贡献
- 右子树给它多少贡献
然后才能决定：
- 当前节点作为拐点时答案是多少
- 向父节点汇报多少
这就是非常典型的后序递归。
易错点
最大路径和最容易错的地方
- 返回给父节点时只能选左右一边，不能把两边都带上去。
- 全局答案和递归返回值不是同一个东西。
- 所有节点都为负数时，答案是其中最大的那个负数，所以全局初值不能写成
0。
复杂度
| 方法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 递归 | O(n) | O(h) |