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

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

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

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

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

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

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

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

输出:11。

答案2024-04-17:

来自左程云

灵捷3.5

大体步骤如下:

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

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

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)

在这里插入图片描述

本作品采用《CC 协议》,转载必须注明作者和本文链接
微信公众号:福大大架构师每日一题。最新面试题,涉及golang,rust,mysql,redis,云原生,算法,分布式,网络,操作系统。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!
未填写
文章
477
粉丝
23
喜欢
37
收藏
22
排名:454
访问:2.0 万
私信
所有博文
社区赞助商