完全二叉树是每一层（除最后一层外）都是完全填充（即，结点数达到最大）的，并且所有的结点都尽可能地集中在左侧。
设计一个用完全二叉树初始化的数据结构 CBTInserter，它支持以下几种操作：
CBTInserter(TreeNode root) 使用头结点为 root 的给定树初始化该数据结构；
CBTInserter.insert(int v) 将 TreeNode 插入到存在值为 node.val = v 的树中以使其保持完全二叉树的状态，并返回插入的 TreeNode 的父结点的值；
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 之间。
思路：我们标记最下边一层需要放多少个和已经放了多少个，若放满了就再加一层，对于具体放在最底层的那个位置，我们考虑类似于二分查找的模式，例如：最底层放满需要8个元素，目前已经放了5个了，现在需要放第六个元素。则第一次应该走到根节点的右子树，因为左子树的最底层最多也只能放4个元素，则我们将右子树的树根当做根节点，而因为左子树已经包含了4个元素，因此在当前子树中最底层只用将待插元素放在第6-4个位置上即可，其实你可以发现问题已经归结为子问题了，进一下向下也是一样的。
class CBTInserter {int sum;int size=0,nowNum;TreeNode root,start;public CBTInserter(TreeNode root) {sum=0;start=root;this.root=root;dfs(this.root);int len=0,sm=0;while(sm+(1<<len)<=sum) {sm+=1<<len;len++;}root=start;nowNum=sum-sm+1; size=1<<len;}private void dfs(TreeNode root) {if(root==null) return;sum++;dfs(root.left);dfs(root.right);}public int insert(int v) {root=start;int tmp1=nowNum,tmp2=size;while(root!=null) {if(tmp1>tmp2/2) {tmp1-=tmp2/2;if(tmp2>2)root=root.right;else {root.right=new TreeNode(v);break;}}else {if(tmp2>2)root=root.left;else {root.left=new TreeNode(v);break;}}tmp2/=2;}if(nowNum==size) {size*=2;nowNum=1;}elsenowNum++;return root.val;}public TreeNode get_root() {return start;}
}
