2024-04-17：用go语言，欢迎各位勇者莅临力扣城，本次的挑战游戏名为「力扣泡泡龙」。 游戏的起点是一颗形状如二叉树的泡泡
2024-04-17：用go语言，欢迎各位勇者莅临力扣城，本次的挑战游戏名为「力扣泡泡龙」。 游戏的起点是一颗形状如二叉树的泡泡
福大大架构师每日一题
发布于 2024-04-18 12:54:26
发布于 2024-04-18 12:54:26
游戏的起点是一颗形状如二叉树的泡泡树，其中每个节点的值代表该泡泡的分值。勇者们有一次机会可以击破一个节点泡泡，但需要满足以下规则：
被击破的节点泡泡最多只能有一个子节点泡泡。
如果被击破的节点泡泡有子节点泡泡，那么这个子节点泡泡将会取代被击破泡泡的位置，也就是说，整棵以被击破泡泡为根的子树将会上移。
我们的任务是计算在进行了这样一个击破操作（或选择不击破任何节点）后，这棵二叉泡泡树的最大「层和」是多少。
这里的「层和」是指：在同一高度的所有节点泡泡的分值之和。
输入：root = [6,0,3,null,8]。
输出：11。
答案2024-04-17：
来自左程云。
灵捷3.5
大体步骤如下：
1.定义节点结构体 TreeNode 和信息结构体 Info。
2.定义全局变量 levelInfos 和 jobs，分别代表每个层级的信息和待处理的节点。
3.定义作业结构体 Job，包含节点的ID和层级。
4.实现 getMaxLayerSum 函数，计算二叉泡泡树的最大层和。
5.在 getMaxLayerSum 函数中，初始化全局变量，计算树的高度。
6.遍历每个层级，计算该层级最后一个节点的分值和。
7.遍历所有待处理的节点，根据节点的ID、层级和左右边界，计算当前层级的节点和下一层级的节点。
8.根据题目描述的规则，更新最大层和的结果。
9.返回最终的最大层和。
总的时间复杂度为 O(N)，其中 N 是节点的数量。
总的额外空间复杂度为 O(H)，其中 H 是树的高度。
Go完整代码如下：
package main
import (
"fmt"
"math"
)
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
type Info struct {
preSum int
left int
right int
finshId int
}
var levelInfos [][]Info
var jobs []Job
type Job struct {
nodeId int
level int
}
func getMaxLayerSum(root *TreeNode) int {
levelInfos = nil
jobs = nil
process(root, 0)
height := len(levelInfos) - 1
ans := math.MinInt64
for level := 0; level < height; level++ {
levelList := levelInfos[level]
ans = max(ans, levelList[len(levelList)-1].preSum)
}
for id := 0; id < len(jobs); id++ {
job := jobs[id]
nodeId := job.nodeId
level := job.level
left := nodeId
right := nodeId
curLevelSum := levelInfos[level][left].preSum - levelInfos[level][left-1].preSum
for ; level < height; level++ {
if left > right {
break
}
levelList := levelInfos[level]
if right-left+1 == len(levelList)-1 {
break
}
leftInfo := levelList[left]
rightInfo := levelList[right]
nextLeft := leftInfo.left
nextRight := rightInfo.right
curLevelAll := levelList[len(levelList)-1].preSum
if leftInfo.finshId != -1 && leftInfo.finshId == rightInfo.finshId {
break
}
leftInfo.finshId = rightInfo.finshId
nextLevelSum := 0
if nextLeft <= 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
}
}
return ans
}
func process(cur *TreeNode, level int) bool {
if cur == nil {
return false
}
for level+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
return true
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func main() {
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-*-
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Info:
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 = []
class Job:
def __init__(self, nodeId, level):
self.nodeId = nodeId
self.level = level
def getMaxLayerSum(root):
global levelInfos, jobs
levelInfos = []
jobs = []
process(root, 0)
height = len(levelInfos) - 1
ans = float('-inf')
for level in range(height):
levelList = levelInfos[level]
ans = max(ans, levelList[-1].preSum)
for id in range(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
while level < height:
if left > right:
break
levelList = levelInfos[level]
if right - left + 1 == len(levelList) - 1:
break
leftInfo = levelList[left]
rightInfo = levelList[right]
nextLeft = leftInfo.left
nextRight = rightInfo.right
curLevelAll = levelList[-1].preSum
if leftInfo.finshId != -1 and leftInfo.finshId == rightInfo.finshId:
break
leftInfo.finshId = rightInfo.finshId
nextLevelSum = 0
if nextLeft <= 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
return ans
def process(cur, level):
global levelInfos, jobs
if cur is None:
return False
while level + 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
if not hasLeft or not hasRight:
jobs.append(Job(nodeId, level))
levelList[nodeId].right = len(levelInfos[level+1]) - 1
return True
root = TreeNode(6)
root.left = TreeNode(0)
root.left.right = TreeNode(8)
root.right = TreeNode(3)
result = getMaxLayerSum(root)
print(result)
本文参与?腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2024-04-17，如有侵权请联系?cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录