2022.7.25-----leetcode.919

 TreeNode root;
    Deque<TreeNode> q;//存储最后一个节点的父节点到最后节点
    public CBTInserter(TreeNode root) {
        this.root=root;
        q=new ArrayDeque<>();
        if(root!=null)
            q.add(root);
        while(!q.isEmpty()){
            TreeNode n=q.getFirst();
            if(n.left!=null)
                q.add(n.left);
            else break;
            if(n.right!=null)
                q.add(n.right);
            else break;
            q.poll();
        }
    }
    
    public int insert(int val) {
        TreeNode n=q.getFirst();
        if(n.left==null){
            n.left=new TreeNode(val);
            q.add(n.left);         
        }else{
            n.right=new TreeNode(val);
            q.add(n.right);
            q.poll();
        }
        return n.val;
    }
    public TreeNode get_root() {
        return root;
    }