欢迎各位勇者来到力扣城,本次试炼主题为「力扣泡泡龙」。
游戏初始状态的泡泡形如二叉树 root
,每个节点值对应了该泡泡的分值。勇者最多可以击破一个节点泡泡,要求满足:
注:即整棵子树泡泡上移
请问在击破一个节点泡泡操作或无击破操作后,二叉泡泡树的最大「层和」是多少。
注意:
示例 1:
输入:
root = [6,0,3,null,8]
输出:
11
解释:勇者的最佳方案如图所示
示例 2:
输入:
root = [5,6,2,4,null,null,1,3,5]
输出:
9
解释:勇者击破 6 节点,此时「层和」最大为 3+5+1 = 9
示例 3:
输入:
root = [-5,1,7]
输出:
8
解释:勇者不击破节点,「层和」最大为 1+7 = 8
提示:
2 <= 树中节点个数 <= 10^5
-10000 <= 树中节点的值 <= 10000