写点什么

2024-04-17:用 go 语言,欢迎各位勇者莅临力扣城,本次的挑战游戏名为「力扣泡泡龙」。 游戏的起点是一颗形状如二叉树的泡泡树,其中每个节点的值代表该泡泡的分值。勇者们有一次机会可以击破一个节点泡

  • 2024-04-17
    北京
  • 本文字数:3263 字

    阅读完需:约 11 分钟

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 [][]Infovar 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)
复制代码



发布于: 刚刚阅读数: 5
用户头像

公众号:福大大架构师每日一题 2021-02-15 加入

公众号:福大大架构师每日一题

评论

发布
暂无评论
2024-04-17:用go语言,欢迎各位勇者莅临力扣城,本次的挑战游戏名为「力扣泡泡龙」。 游戏的起点是一颗形状如二叉树的泡泡树,其中每个节点的值代表该泡泡的分值。勇者们有一次机会可以击破一个节点泡_福大大架构师每日一题_福大大架构师每日一题_InfoQ写作社区