完全二叉树是每一层(除最后一层外)都是完全填充(即,节点数达到最大,第 n 层有 2n-1 个节点)的,
并且所有的节点都尽可能地集中在左侧。
设计一个用完全二叉树初始化的数据结构 CBTInserter,它支持以下几种操作:
CBTInserter(TreeNode root) 使用根节点为 root 的给定树初始化该数据结构;
CBTInserter.insert(int v) 向树中插入一个新节点,节点类型为 TreeNode,值为 v 。
使树保持完全二叉树的状态,并返回插入的新节点的父节点的值;
CBTInserter.get_root() 将返回树的根节点。
示例 1:输入:inputs = ["CBTInserter","insert","get_root"], inputs = [[[1]],[2],[]] 输出:[null,1,[1,2]]
示例 2:输入:inputs = ["CBTInserter","insert","insert","get_root"], inputs = [[[1,2,3,4,5,6]],[7],[8],[]]
输出:[null,3,4,[1,2,3,4,5,6,7,8]]
提示:最初给定的树是完全二叉树,且包含 1 到 1000 个节点。
每个测试用例最多调用 CBTInserter.insert 操作 10000 次。
给定节点或插入节点的每个值都在 0 到 5000 之间。
注意:本题与主站 919 题相同:
1、广度优先搜索;时间复杂度O(n),空间复杂度O(n)
type CBTInserter struct {
root *TreeNode
arr []*TreeNode
}
func Constructor(root *TreeNode) CBTInserter {
arr := make([]*TreeNode, 0)
queue := make([]*TreeNode, 0)
arr = append(arr, root)
queue = append(queue, root)
for len(queue) > 0 {
length := len(queue)
for i := 0; i < length; i++ {
if queue[i].Left != nil {
queue = append(queue, queue[i].Left)
arr = append(arr, queue[i].Left)
}
if queue[i].Right != nil {
queue = append(queue, queue[i].Right)
arr = append(arr, queue[i].Right)
}
}
queue = queue[length:]
}
return CBTInserter{root: root, arr: arr}
}
func (this *CBTInserter) Insert(v int) int {
newNode := &TreeNode{Val: v}
this.arr = append(this.arr, newNode)
n := len(this.arr)
target := this.arr[n/2-1]
if n%2 == 0 {
target.Left = newNode
} else {
target.Right = newNode
}
return target.Val
}
func (this *CBTInserter) Get_root() *TreeNode {
return this.root
}
Medium题目,题目同leetcode 919.完全二叉树插入器
页面更新:2024-03-02
本站资料均由网友自行发布提供,仅用于学习交流。如有版权问题,请与我联系,QQ:4156828
© CopyRight 2020-2024 All Rights Reserved. Powered By 71396.com 闽ICP备11008920号-4
闽公网安备35020302034903号