https://leetcode.com/problems/complete-binary-tree-inserter/
给出树节点的定义和完全二叉树插入器类的定义，为这个类补全功能。完全二叉树的定义为：这颗二叉树除最后一层外左右层的节点都是满的(对于第i层有2^(i-1)个节点)，最后一层节点都出现在尽量靠左的位置。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class CBTInserter {
public:
CBTInserter(TreeNode* root) {}
int insert(int v) {}
TreeNode* get_root() {}
};
/**
* Your CBTInserter object will be instantiated and called as such:
* CBTInserter* obj = new CBTInserter(root);
* int param_1 = obj->insert(v);
* TreeNode* param_2 = obj->get_root();
解法一：
我的思路是，先遍历给定二叉树，得到树的深度maxlayer和最后一层的节点数numoflastlayer。若numoflastlayer<2^(maxlayer-1)，则新节点插入在第layer=maxlayer层；若numoflastlayer=2^(maxlayer-1)，说明最后一层满了，需要插入到第layer=maxlayer+1层。再先序遍历这棵树，遍历到第layer-1层的节点时，判断：若节点只有左节点，则将新节点作为其右孩子；若节点无子节点，则将新节点作为其左孩子。
class CBTInserter
{
public:
void preorder(TreeNode* root,int layer)
{
if(layer>maxlayer)
{
maxlayer = layer;
numoflastlayer = ;
}
else if(layer == maxlayer)
numoflastlayer++;
if(root->left!=NULL)
preorder(root->left, layer+);
if(root->right!=NULL)
preorder(root->right, layer+);
}
CBTInserter(TreeNode* root)
{
root_ =root;
maxlayer=-;
numoflastlayer=;
preorder(root,);
} TreeNode* Insert(TreeNode* root, int v, int layer, int insertlayer)
{
if(layer == insertlayer-)
{
if(root->left == NULL)
{
root->left = new TreeNode(v);
return root;
}
else if(root->right == NULL)
{
root->right = new TreeNode(v);
return root;
}
}
else
{
TreeNode* res = Insert(root->left, v, layer+, insertlayer);
if(res == NULL)
res = Insert(root->right, v, layer+, insertlayer);
return res;
}
return NULL;
} int insert(int v)
{
cout<<v<<endl;
int maxnumoflastlayer = pow(, maxlayer);
TreeNode* res = NULL;
if(numoflastlayer<maxnumoflastlayer)
{
res = Insert(root_,v,, maxlayer);
numoflastlayer++;
}
else
{
res = Insert(root_,v,,maxlayer+);
maxlayer++;
numoflastlayer=;
}
return res->val;
} TreeNode* get_root()
{
return root_;
}
private:
TreeNode* root_;
int maxlayer;
int numoflastlayer;
};
解法二：新节点插入的位置的父节点的子节点数要么为1，要么为0。根据层次遍历，把节点子节点数为0或1的节点存入队列。插入时，取队头节点，若该节点有左孩子，则将新节点作为其右孩子，并将该左右孩子压入队尾，将该队头节点出队；若该节点无孩子，则将新节点作为其左孩子，该节点仍然作为队头节点。
class CBTInserter
{
public:
TreeNode* root_;
queue<TreeNode*> nodes_0_1;
CBTInserter(TreeNode* root)
{
root_ = root;
queue<TreeNode*> que;
que.push(root);
while(!que.empty())
{
TreeNode* now = que.front();
que.pop();
if(now->left == NULL)
nodes_0_1.push(now);
else if(now->right == NULL)
nodes_0_1.push(now);
else
{
que.push(now->left);
que.push(now->right);
}
}
} int insert(int v)
{
TreeNode* root = nodes_0_1.front();
if(root->left!=NULL)
{
root->right = new TreeNode(v);
nodes_0_1.pop();
nodes_0_1.push(root->left);
nodes_0_1.push(root->right);
}
else
root->left = new TreeNode(v);
return root->val;
} TreeNode* get_root()
{
return root_;
}
};