LeetCode 124. 二叉树中的最大路径和
题目描述
题意分析
在一棵非空二叉树中选择一条非空路径，使路径上所有节点值的和最大，返回这个最大和。路径的相邻节点必须由一条父子边连接，同一个节点最多出现一次。
起点和终点可以是任意节点，不要求经过根，也不要求从根走到叶子；路径可以只有一个节点，也可以从某个节点的一侧子树走到它的另一侧。它必须是一条连续的路线，不能在一个节点处分出三条支路。节点值可以为负，全部为负时也必须选择至少一个节点，不能用空路径的和
0作为答案。
解法：后序 DFS 计算单边贡献
核心思路
[!blue]
先区分两个问题：一是当前子树能向父节点提供多大的路径和，二是已经遇到的完整路径中哪个最好。它们不能使用同一个返回值，因为一条路径接上父节点后，当前节点最多还能向下接一个孩子；如果左右孩子都接，再接父节点，就会在当前节点处分叉。
定义
gain(node)为：必须包含node，从它开始向下走、至多选择一侧子树时能得到的最大和。这个值允许为负，因为当前节点必须被包含。先递归求出左右孩子的贡献，再分别取left = max(0, gain(node.left))、right = max(0, gain(node.right))；负贡献只会降低总和，可以选择不连接那一侧。当前节点向父节点返回的贡献是
node.val + max(left, right)，只能选左右两侧中较好的一侧。另一方面，如果完整路径就在当前节点处向两边展开、不再接父节点，那么左右两侧都可以使用，候选答案就是node.val + left + right。用它更新全局最大值best，再返回单边贡献。任意合法路径都有一个离根最近的节点。以这个节点为分界，路径最多包含左子树中的一条向下路线、节点本身，以及右子树中的一条向下路线；恰好对应上述候选形式。遍历所有节点，相当于枚举了所有可能的分界点，因此也能找到完全位于某棵子树中的最优路径。
左右贡献必须先计算完，当前节点才能合并，所以采用后序 DFS。
best初始化为根节点值，每个候选都包含当前真实节点，保证全负树仍会选出最大的节点值。被截为零的是可不选的子树贡献，不能把整条路径也当成可空选。
解题步骤
- 用
root.val初始化best，随后从根节点调用gain。- 遇到空节点返回
0，表示这一侧没有可连接的节点。- 递归计算左右孩子的贡献，并分别将负贡献置为
0。- 用
node.val + left + right更新best，表示当前节点作为路径最高点时的最大路径和。- 返回
node.val + max(left, right)，供父节点连接当前节点和其中一侧路径。- 遍历完成后返回
best，而不是根节点的单边贡献。
代码实现
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)$，
n为节点数。每个节点只进行一次左右贡献合并和答案更新。- 空间复杂度：$O(h)$，
h为树高，来自递归调用栈。平衡树为 $O(\log n)$，退化成链时为 $O(n)$。
关键点总结
[!green]
- 返回给父节点的是以当前节点为端点的单边贡献，全局答案记录可以连接两侧的完整路径。
- 每条路径都有唯一的最高节点，逐节点合并左右贡献就能覆盖所有候选路径。
- 可以舍弃负的子树贡献，但每个候选必须包含当前节点；用真实节点值初始化答案。
易错点总结
[!yellow]
- 把
best初始化为0，会让全负树错误地返回不存在的空路径。- 将
node.val + left + right返回给父节点，会把三条支路拼在一起，不再是合法路径。- 只使用根节点的返回值，会漏掉不经过根的路径，也会漏掉在某个节点处连接左右两侧的路径。
- 左右贡献需要分别与
0取最大值；直接把负贡献一起相加，会让本可不连接的子树降低答案。- Java 中
best是成员变量，必须在每次maxPathSum调用时重置，避免同一对象处理下一棵树时沿用旧结果。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 543. 二叉树的直径 | 简单 | 同样在节点处组合左右子路径，并只向父节点返回单侧贡献；原题计边数，本题累加节点值。 |
| 687. 最长同值路径 | 中等 | 同样寻找可能跨过某节点的最长路径，原题要求相邻节点同值，本题按权值和取最优。 |
| 104. 二叉树的最大深度 | 简单 | 后序返回子树高度并在根处合并信息；本题舍弃负贡献后合并最大路径和，该题取两侧最大高度加一。 |
| 110. 平衡二叉树 | 简单 | 后序返回子树高度并在根处合并信息；本题舍弃负贡献后合并最大路径和，该题额外验证两侧高度差。 |