Skip to content

Files

Latest commit

9fcd034 · Apr 6, 2023

History

History

LCP 60. 力扣泡泡龙

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
Nov 30, 2022
Apr 6, 2023

题目描述

欢迎各位勇者来到力扣城,本次试炼主题为「力扣泡泡龙」。

游戏初始状态的泡泡形如二叉树 root,每个节点值对应了该泡泡的分值。勇者最多可以击破一个节点泡泡,要求满足:

  • 被击破的节点泡泡 至多 只有一个子节点泡泡
  • 当被击破的节点泡泡有子节点泡泡时,则子节点泡泡将取代被击破泡泡的位置

    注:即整棵子树泡泡上移

请问在击破一个节点泡泡操作或无击破操作后,二叉泡泡树的最大「层和」是多少。

注意:

  • 「层和」为同一高度的所有节点的分值之和

示例 1:

输入:root = [6,0,3,null,8]

输出:11

解释:勇者的最佳方案如图所示
image.png

示例 2:

输入:root = [5,6,2,4,null,null,1,3,5]

输出:9

解释:勇者击破 6 节点,此时「层和」最大为 3+5+1 = 9
image.png

示例 3:

输入:root = [-5,1,7]

输出:8

解释:勇者不击破节点,「层和」最大为 1+7 = 8

提示

  • 2 <= 树中节点个数 <= 10^5
  • -10000 <= 树中节点的值 <= 10000

解法

Python3

Java

...