type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
二叉树中的 路径 被定义为一条节点序列,序列中每对相邻节点之间都存在一条边。
同一个节点在一条路径序列中 至多出现一次 。路径 至少包含一个 节点,且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点
root ,返回其 最大路径和 。示例 1:

示例 2:

解法一:后序递归(推荐)
把“路径”理解成:从某个节点出发,沿父子指针走,中途不拐回头,可以穿过某个“拐点”节点向两边各走一次,但整条路径是连通的。
对任一节点
x,关心两件事:- 作为“向上延伸”的一条链,它能给父节点贡献多大?
只能从
x 选 左链或右链 里较大的一条再加上 x.val;如果这条贡献是负数,干脆不要(当作 0)。
- 以
x为最高点(拐点)时,这里能形成多大的完整路径?
x.val + max(0, leftGain) + max(0, rightGain)。这个值用来更新全局答案。复杂度
- 时间:
O(n),每个节点访问一次。
- 空间:
O(h),递归栈(h为树高;最坏退化链表为O(n))。
解法二:后序递归
不用全局变量,把“向上单链最大增益”和“当前子树内的最佳答案”一起返回。
这样父节点在合并时,同时拿到两侧的信息,自己再计算本子树内的最优。
定义返回二元组
(up, best):up:从当前节点向父节点能提供的单链最大增益(负数截断为 0 的思想同上);
best:当前整棵子树内部的最大路径和。
复杂度
- 时间:
O(n)
- 空间:
O(h)
解法三:后序迭代
递归本质是“后序遍历 + 回传值”,可以用两次栈或“颜色标记法”迭代实现:
- 用哈希表
gain[node]存每个节点的“向上单链最大增益”;
- 出栈时才有左右孩子的增益,按解法一的公式更新全局答案,并写回
gain[node]。
适合不允许递归或需要解决栈溢出的问题。
复杂度
- 时间:
O(n)
- 空间:
O(n)(显式栈 + 字典;平均仍与树高相关)
- Author:Fan Luo
- URL:https://fanluo.me/article/leetcode-124-二叉树中的最大路径和
- Copyright:All articles in this blog adopt BY-NC-SA agreement. Please indicate the source!
上一篇
[Leetcode 123] 买卖股票的最佳时机 III
下一篇
[Leetcode 126] 单词接龙 II