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

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

    CBTInserter(TreeNode root) 使用根节点为 root 的给定树初始化该数据结构；
    CBTInserter.insert(int v) 向树中插入一个新节点，节点类型为 TreeNode，值为 v 。使树保持完全二叉树的状态，并返回插入的新节点的父节点的值；
    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. class CBTInserter {
    2.     /**
    3.     本题采用队列数据结构，层序遍历的方式求解，初始化时，我们找到第一个
    4.     左孩子空或者都为空的节点，之前的节点出队，新节点插入道该节点的左孩子
    5.     或者右孩子，左孩子直接插入，右孩子插入后需要把父节点出队，再将左右孩子
    6.     入队
    7.      */
    8.     Deque<TreeNode> queue;
    9.     TreeNode head;
    10.     public CBTInserter(TreeNode root) {
    11.         head = root;
    12.         queue = new LinkedList<>();
    13.         queue.addLast(root);
    14.         //找到下一个插入点
    15.         while (queue.peekFirst().left != null && queue.peekFirst().right != null) {
    16.             TreeNode node = queue.pollFirst();
    17.             queue.addLast(node.left);
    18.             queue.addLast(node.right);
    19.         }
    20.     }
    22.     public int insert(int v) {
    23.         TreeNode node = queue.peekFirst();
    24.         TreeNode cur = new TreeNode(v);
    25.         //左节点为空直接插入
    26.         if (node.left == null) 
    27.             node.left = cur;
    28.         //右节点需要将父节点出队，左右孩子入队
    29.         else {
    30.             node.right = cur;
    31.             queue.pollFirst();
    32.             queue.addLast(node.left);
    33.             queue.addLast(node.right);
    34.         }
    35.         return node.val;
    36.     }
    38.     public TreeNode get_root() {
    39.         return head;
    40.     }   
    41. }