完全二叉树是每一层（除最后一层外）都是完全填充（即，结点数达到最大）的，并且所有的结点都尽可能地集中在左侧。
设计一个用完全二叉树初始化的数据结构 CBTInserter，它支持以下几种操作：
CBTInserter(TreeNode root) 使用头结点为 root 的给定树初始化该数据结构；
CBTInserter.insert(int v) 将 TreeNode 插入到存在值为 node.val = v 的树中以使其保持完全二叉树的状态，并返回插入的 TreeNode 的父结点的值；
CBTInserter.get_root() 将返回树的头结点。
示例 1：
代码语言：javascript复制输入：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位置是队首
代码实现
代码语言：javascript复制/**
* 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();
*/
