# 0919. Complete Binary Tree Inserter
###### tags: `Leetcode` `Medium` `FaceBook` `Complete Binary Tree`
Link: https://leetcode.com/problems/complete-binary-tree-inserter/

## 思路 CBTInserter O(N) insert O(1)
一开始看错条件了 不知道CBTInserter传进来的一定是complete binary tree，所以花了很长时间
因为一开始传进来的就是complete binary tree，所以一旦找到一个node，它的child没满，后面的一定都没满，所以CBTInserter的职责就是找到第一个incomplete node，queue里面就存所有child还没有满的node

## Code

class CBTInserter {
    TreeNode root;
    Queue<TreeNode> q;
    public CBTInserter(TreeNode root) {
        this.root = root; 
        q = new LinkedList<>();
        if(root != null){
            q.add(root);
            while(!q.isEmpty()){
                TreeNode curr = q.peek();
                if(curr.left!=null && curr.right!=null){
                    q.add(curr.left);
                    q.add(curr.right);
                    q.poll();
                }
                else{
                    break;
                }
            }
        }
    }
    
    public int insert(int val) {
        TreeNode incompleteNode = q.peek();
        TreeNode newNode = new TreeNode(val);
        if(incompleteNode.left == null){
            incompleteNode.left = newNode;
        }
        else{
            incompleteNode.right = newNode;
        }
        if(incompleteNode.right!=null){
            q.poll();
            q.add(incompleteNode.left);
            q.add(incompleteNode.right);
        }
        
        return incompleteNode.val;
    }
    
    public TreeNode get_root() {
        return root;
    }
}