[Leetcode 124] 二叉树中的最大路径和

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

解法一:后序递归(推荐)

把“路径”理解成:从某个节点出发,沿父子指针走,中途不拐回头,可以穿过某个“拐点”节点向两边各走一次,但整条路径是连通的。
对任一节点 x,关心两件事:
  1. 作为“向上延伸”的一条链,它能给父节点贡献多大?
    1. 只能从 x左链或右链 里较大的一条再加上 x.val
      如果这条贡献是负数,干脆不要(当作 0)。
  1. x 为最高点(拐点)时,这里能形成多大的完整路径
    1. 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)(显式栈 + 字典;平均仍与树高相关)
上一篇
[Leetcode 123] 买卖股票的最佳时机 III
下一篇
[Leetcode 126] 单词接龙 II