golang刷leetcode 经典（12） 完全二叉树插入器

完全二叉树是每一层（除最后一层外）都是完全填充（即，结点数达到最大）的，并且所有的结点都尽可能地集中在左侧。

设计一个用完全二叉树初始化的数据结构 CBTInserter，它支持以下几种操作：

CBTInserter(TreeNode root) 使用头结点为 root 的给定树初始化该数据结构；

CBTInserter.insert(int v) 将 TreeNode 插入到存在值为 node.val = v 的树中以使其保持完全二叉树的状态，并返回插入的 TreeNode 的父结点的值；

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 之间。

解题思路

1，对于完全二叉树类型的题目，一般解法有俩：

A，用数字记录下标index

B，双端队列层序遍历

2，对于本题采用B方案

3，数据结构设计

A，用root存储树的根节点

B，用current存储当前要插入孩子的节点，即新数据的插入位置

C，dqueue 依次存储孩子不满的节点

4，需要注意的坑

A，如果左孩子为空，则下次插入左孩子

B，如果右孩子为空，构建的时候不要忘了把左孩子入队列

C，如果右孩子为空，插入元素后，下一个current位置是队首

代码实现

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
type CBTInserter struct {
    root *TreeNode
    current *TreeNode
    dqueue []*TreeNode
}

func (this* CBTInserter)pop()*TreeNode{
   d:=this.dqueue[0]
   this.dqueue=this.dqueue[1:]
   return d
}

func(this*CBTInserter)push(n*TreeNode){
    this.dqueue=append(this.dqueue,n)
}

func(this*CBTInserter)empty()bool{
    return len(this.dqueue)==0
}
func(this*CBTInserter)Print(){
    fmt.Println("")
    for _,v:=range this.dqueue{
        fmt.Print(v.Val)
    }
}


func Constructor(root *TreeNode) CBTInserter {
    cbt:=CBTInserter{
        root:root,
        current:root,
    }
    if root==nil{
        return cbt
    }
    cbt.push(root)
    for !cbt.empty(){
        node:=cbt.pop()
        if node.Left==nil {
            cbt.current=node
            //cbt.Print()
            return cbt
        }
        if node.Right==nil{
            cbt.current=node
            cbt.push(node.Left)
            return cbt
        }
        cbt.push(node.Left)
        cbt.push(node.Right)
    }
    //cbt.Print()
    return cbt
}


func (this *CBTInserter) Insert(v int) int {
    n:=&TreeNode{
        Val:v,
    }
    if this.root==nil{
        this.root=n
        this.current=n
        return v
    }
    var val int
    if this.current.Left==nil{
        this.current.Left=n
        val=this.current.Val
    }else{
    //if this.current.Right==nil{
       this.current.Right=n
        val=this.current.Val
        //this.Print()
        if !this.empty(){
            this.current=this.pop()
        }
    }
    this.push(n)
    return val
}


func (this *CBTInserter) Get_root() *TreeNode {
    return this.root
}


/**
 * Your CBTInserter object will be instantiated and called as such:
 * obj := Constructor(root);
 * param_1 := obj.Insert(v);
 * param_2 := obj.Get_root();
 */

复制