2024-04-17：用go语言，欢迎各位勇者莅临力扣城，本次的挑战游戏

2024-04-17：用go语言，欢迎各位勇者莅临力扣城，本次的挑战游戏名为「力扣泡泡龙」。

游戏的起点是一颗形状如二叉树的泡泡树，其中每个节点的值代表该泡泡的分值。勇者们有一次机会可以击破一个节点泡泡，但需要满足以下规则：

被击破的节点泡泡最多只能有一个子节点泡泡。

如果被击破的节点泡泡有子节点泡泡，那么这个子节点泡泡将会取代被击破泡泡的位置，也就是说，整棵以被击破泡泡为根的子树将会上移。

我们的任务是计算在进行了这样一个击破操作（或选择不击破任何节点）后，这棵二叉泡泡树的最大「层和」是多少。

这里的「层和」是指：在同一高度的所有节点泡泡的分值之和。

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

输出：11。

答案2024-04-17：

来自左程云。

灵捷3.5

大体步骤如下：

1.定义节点结构体和信息结构体。

TreeNode

Info

2.定义全局变量和，分别代表每个层级的信息和待处理的节点。

levelInfos

jobs

3.定义作业结构体，包含节点的ID和层级。

Job

4.实现函数，计算二叉泡泡树的最大层和。

getMaxLayerSum

5.在函数中，初始化全局变量，计算树的高度。

getMaxLayerSum

6.遍历每个层级，计算该层级最后一个节点的分值和。

7.遍历所有待处理的节点，根据节点的ID、层级和左右边界，计算当前层级的节点和下一层级的节点。

8.根据题目描述的规则，更新最大层和的结果。

9.返回最终的最大层和。

总的时间复杂度为 O(N)，其中 N 是节点的数量。

总的额外空间复杂度为 O(H)，其中 H 是树的高度。

Go完整代码如下：

packagemain
import(
"fmt"
"math"
)
typeTreeNodestruct{
Valint
Left*TreeNode
Right*TreeNode
}
typeInfostruct{
preSumint
leftint
rightint
finshIdint
}
varlevelInfos[][]Info
varjobs[]Job
typeJobstruct{
nodeIdint
levelint
}
funcgetMaxLayerSum(root*TreeNode)int{
levelInfos=nil
jobs=nil
process(root,0)
height:=len(levelInfos)-1
ans:=math.MinInt64
forlevel:=0;levellevelList:=levelInfos[level]
ans=max(ans,levelList[len(levelList)-1].preSum)
}
forid:=0;idjob:=jobs[id]
nodeId:=job.nodeId
level:=job.level
left:=nodeId
right:=nodeId
curLevelSum:=levelInfos[level][left].preSum-levelInfos[level][left-1].preSum
for;levelifleft>right{
break
}
levelList:=levelInfos[level]
ifright-left+1==len(levelList)-1{
break
}
leftInfo:=levelList[left]
rightInfo:=levelList[right]
nextLeft:=leftInfo.left
nextRight:=rightInfo.right
curLevelAll:=levelList[len(levelList)-1].preSum
ifleftInfo.finshId!=-1&&leftInfo.finshId==rightInfo.finshId{
break
}
leftInfo.finshId=rightInfo.finshId
nextLevelSum:=0
ifnextLeft<=nextRight{
nextLevelSum=levelInfos[level+1][nextRight].preSum-levelInfos[level+1][nextLeft-1].preSum
}
ans=max(ans,curLevelAll-curLevelSum+nextLevelSum)
left=nextLeft
right=nextRight
curLevelSum=nextLevelSum
}
}
returnans
}
funcprocess(cur*TreeNode,levelint)bool{
ifcur==nil{
returnfalse
}
forlevel+1>=len(levelInfos){
levelInfos=append(levelInfos,[]Info{{0,-1,-1,-1}})
}
levelList:=levelInfos[level]
preId:=len(levelList)-1
levelList=append(levelList,Info{levelList[preId].preSum+cur.Val,len(levelInfos[level+1]),-1,-1})
levelInfos[level]=levelList
hasLeft:=process(cur.Left,level+1)
hasRight:=process(cur.Right,level+1)
nodeId:=len(levelList)-1
if!hasLeft||!hasRight{
jobs=append(jobs,Job{nodeId,level})
}
levelList[nodeId].right=len(levelInfos[level+1])-1
returntrue
}
funcmax(a,bint)int{
ifa>b{
returna
}
returnb
}
funcmain(){
root:=&TreeNode{
Val:6,
Left:&TreeNode{
Val:0,
Right:&TreeNode{Val:8},
},
Right:&TreeNode{
Val:3,
},
}
result:=getMaxLayerSum(root)
fmt.Println(result)
}

Python完整代码如下：

#-*-coding:utf-8-*-
classTreeNode:
def__init__(self,val=0,left=None,right=None):
self.val=val
self.left=left
self.right=right
classInfo:
def__init__(self,preSum=0,left=-1,right=-1,finshId=-1):
self.preSum=preSum
self.left=left
self.right=right
self.finshId=finshId
levelInfos=[]
jobs=[]
classJob:
def__init__(self,nodeId,level):
self.nodeId=nodeId
self.level=level
defgetMaxLayerSum(root):
globallevelInfos,jobs
levelInfos=[]
jobs=[]
process(root,0)
height=len(levelInfos)-1
ans=float('-inf')
forlevelinrange(height):
levelList=levelInfos[level]
ans=max(ans,levelList[-1].preSum)
foridinrange(len(jobs)):
job=jobs[id]
nodeId=job.nodeId
level=job.level
left=nodeId
right=nodeId
curLevelSum=levelInfos[level][left].preSum-levelInfos[level][left-1].preSum
whilelevelifleft>right:
break
levelList=levelInfos[level]
ifright-left+1==len(levelList)-1:
break
leftInfo=levelList[left]
rightInfo=levelList[right]
nextLeft=leftInfo.left
nextRight=rightInfo.right
curLevelAll=levelList[-1].preSum
ifleftInfo.finshId!=-1andleftInfo.finshId==rightInfo.finshId:
break
leftInfo.finshId=rightInfo.finshId
nextLevelSum=0
ifnextLeft<=nextRight:
nextLevelSum=levelInfos[level+1][nextRight].preSum-levelInfos[level+1][nextLeft-1].preSum
ans=max(ans,curLevelAll-curLevelSum+nextLevelSum)
left=nextLeft
right=nextRight
curLevelSum=nextLevelSum
level+=1
returnans
defprocess(cur,level):
globallevelInfos,jobs
ifcurisNone:
returnFalse
whilelevel+1>=len(levelInfos):
levelInfos.append([Info(0,-1,-1,-1)])
levelList=levelInfos[level]
preId=len(levelList)-1
levelList.append(Info(levelList[preId].preSum+cur.val,len(levelInfos[level+1]),-1,-1))
hasLeft=process(cur.left,level+1)
hasRight=process(cur.right,level+1)
nodeId=len(levelList)-1
ifnothasLeftornothasRight:
jobs.append(Job(nodeId,level))
levelList[nodeId].right=len(levelInfos[level+1])-1
returnTrue
root=TreeNode(6)
root.left=TreeNode(0)
root.left.right=TreeNode(8)
root.right=TreeNode(3)
result=getMaxLayerSum(root)
print(result)