919. 完全二叉树插入器.md

919. 完全二叉树插入器

题目传送门

点击这里

解题思路

首先这道题要清楚什么为完全二叉树，是尽可能完全填充，新节点优先加入到最后一层的左节点中，所以这道题需要判断每一层的情况，从上到下遍历，优先处理左节点，所以使用的是队列。队列中维护的是可插入新节点的节点，且要满足左先右后的规则。

代码

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


func Constructor(root *TreeNode) CBTInserter {
    q := []*TreeNode{root}
    queue := []*TreeNode{}
    // 从根节点从上向下遍历
    for len(q) > 0 {
        node := q[0]
        q = q[1:]
        // 如果左右节点不为nil，则添加到q中继续向下遍历，且要按照左先，右后的顺序加入队列中遍历
        if node.Left != nil {
            q = append(q, node.Left)
        }
        if node.Right != nil {
            q = append(q, node.Right)
        }
        // 如果节点的左或右节点为nil，则可以填入queue，作为可插入的节点，在整体遍历过程中，先加入的节点作为优先可插入的节点
        if node.Right == nil || node.Left == nil {
            queue = append(queue, node)
        }
    }
    return CBTInserter{root, queue}
}


func (this *CBTInserter) Insert(val int) int {
    node := this.queue[0]
    if node.Left == nil {
        node.Left = &TreeNode{val, nil, nil}
        // 记得将新加入的节点加入到可插入的队列中
        this.queue = append(this.queue, node.Left)
    } else {
        // 如果其右节点为nil，我们插入了后该节点的子节点就满了，从可插入的队列中删除
        this.queue = this.queue[1:]
        node.Right = &TreeNode{val, nil, nil}
        this.queue = append(this.queue, node.Right)
    }
    return node.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(val);
 * param_2 := obj.Get_root();
 */