LeetCode LCR 051. 二叉树中的最大路径和
题目描述
题意分析
路径可以从任意节点开始和结束，相邻节点通过边连接，同一节点不能重复经过，且至少包含一个节点。要求路径上的节点值总和最大，路径不必经过根，也不必到达叶子。
每条路径都有唯一的最高点，即深度最小的节点。它可以连接左右两条向下的链，任意一侧也可以不选。枚举这个最高点，就能覆盖所有路径形态。
解法：后序计算单边贡献
核心思路
[!blue]
定义
dfs(node)返回从当前节点出发、向下延伸的最大单链和。这个值将交给父节点继续连接，因此当前节点下面只能选择左边或右边，不能同时分叉。先递归得到左右单链和，再分别与 0 取最大，记为
left、right。负贡献只会降低路径和，舍弃对应分支更好；取 0 就表示不连接这一侧。若当前节点是整条路径的最高点，左右两侧都可以连接，候选答案为
node.val+left+right。两条链位于不同子树，没有重复节点，能够组成一条合法路径；在每个节点都结算这个值，就不会漏掉全局最优路径。递归向父节点返回的则是
node.val+max(left,right)。如果把左右贡献都返回，父节点再接上来后，当前节点就会连接三条边，不再是一条路径。因此“更新全局答案”和“返回给父节点”必须使用两个不同的值。
解题步骤
- 把答案初始化为低于所有节点值的
-1001，再开始后序递归。- 空节点返回 0；非空节点递归左右孩子，并舍弃两侧负贡献。
- 用当前值加左右贡献更新全局答案。
- 返回当前值加较大的单侧贡献，最后由入口返回全局答案。
路径至少包含当前节点，全局答案不能以 0 初始化。全负树会在每处舍弃两侧贡献，最后选出值最大的单节点。
代码实现
class Solution {
private int answer = -1001;
public int maxPathSum(TreeNode root) {
dfs(root);
return answer;
}
private int dfs(TreeNode root) {
if (root == null) {
return 0;
}
int left = Math.max(0, dfs(root.left));
int right = Math.max(0, dfs(root.right));
answer = Math.max(answer, root.val + left + right);
return root.val + Math.max(left, right);
}
}
func maxPathSum(root *TreeNode) int {
answer := -1001
var dfs func(*TreeNode) int
dfs = func(root *TreeNode) int {
if root == nil {
return 0
}
left := max(0, dfs(root.Left))
right := max(0, dfs(root.Right))
answer = max(answer, left+right+root.Val)
return max(left, right) + root.Val
}
dfs(root)
return answer
}
复杂度分析
- 时间复杂度：$O(n)$，每个节点只计算一次单链贡献，并结算一次以自身为最高点的路径。
- 空间复杂度：$O(h)$，来自递归栈，$h$ 为树高；链状树最坏为 $O(n)$。
关键点总结
[!green]
- 向上返回一条单链，在当前节点处才能把左右两条链拼成完整候选。
- 分支可以不选，所以负贡献截断为 0；整条路径不能为空，所以答案初值必须为负。
- 最优路径可能完全位于某棵子树，必须保留所有节点处更新出的全局最大值。
易错点总结
[!yellow]
- 向父节点返回的只能是单边最大贡献；当前节点左右两臂之和只用于更新全局答案。
- 负的子树贡献按 0 处理，但全局答案不能初始化为 0，否则全负树错误地选择空路径。
- 每个节点都可能是最优路径的最高点，不能只在根或叶子更新答案。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 543. 二叉树的直径 | 简单 | 同样在节点处组合左右子路径，并只向父节点返回单侧贡献；原题计边数，本题累加节点值。 |
| 687. 最长同值路径 | 中等 | 同样寻找可能跨过某节点的最长路径，原题要求相邻节点同值，本题按权值和取最优。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！