2024-04-17：用 go 语言，欢迎各位勇者莅临力扣城，本次的挑战游戏名为「力扣泡泡龙」。
游戏的起点是一颗形状如二叉树的泡泡树，其中每个节点的值代表该泡泡的分值。勇者们有一次机会可以击破一个节点泡泡，但需要满足以下规则：
被击破的节点泡泡最多只能有一个子节点泡泡。
如果被击破的节点泡泡有子节点泡泡，那么这个子节点泡泡将会取代被击破泡泡的位置，也就是说，整棵以被击破泡泡为根的子树将会上移。
我们的任务是计算在进行了这样一个击破操作（或选择不击破任何节点）后，这棵二叉泡泡树的最大「层和」是多少。
这里的「层和」是指：在同一高度的所有节点泡泡的分值之和。
输入：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 [][]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)
复制代码
评论