https://leetcode.com/problems/complete-binary-tree-inserter/

设计一个CBTInserter，使用给定完全二叉树初始化。三个功能;

• CBTInserter(TreeNode root) initializes the data structure on a given tree with head node root;
• CBTInserter.insert(int v) will insert a TreeNode into the tree with value node.val = v so that the tree remains complete, and returns the value of the parent of the inserted TreeNode;
• CBTInserter.get_root() will return the head node of the tree.

主要涉及完全二叉树的插入。

解法一：dfs based

对给定的完全二叉树，先计算其最大高度maxlayer，以及深度最深的节点数numoflastlayer。如果numoflastlayer<2^(maxlayer-1)，说明应该在maxlayer-1层第一个子节点数小于2的节点插入；如果numoflastlayer==2^(maxlayer-1)，说明应该在maxlayer层第一个子节点处插入，利用dfs可以完成。插入过后及时更新maxlager和numoflastlayer。

class CBTInserter{
public:
    void preorder(TreeNode* root,int layer){
        if(layer>maxlayer){
            maxlayer = layer;
            numoflastlayer = 1;
        }else if(layer == maxlayer)
            numoflastlayer++;
        if(root->left!=NULL)
            preorder(root->left, layer+1);
        if(root->right!=NULL)
            preorder(root->right, layer+1);
    }
    CBTInserter(TreeNode* root){
        root_ =root;
        maxlayer=-1;
        numoflastlayer=0;
        preorder(root,0);
    }
    TreeNode* Insert(TreeNode* root, int v, int layer, int insertlayer){
        if(layer == insertlayer-1){
            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+1, insertlayer);
            if(res == NULL)
                res = Insert(root->right, v, layer+1, insertlayer);
            return res;
        }
        return NULL;
    }
    int insert(int v){int maxnumoflastlayer = pow(2, maxlayer);
        TreeNode* res = NULL;
        if(numoflastlayer<maxnumoflastlayer){
            res = Insert(root_,v,0, maxlayer);
            numoflastlayer++;
        }else{
            res = Insert(root_,v,0,maxlayer+1);
            maxlayer++;
            numoflastlayer=1;
        }
        return res->val;
    }
    TreeNode* get_root(){
        return root_;
    }
private:
    TreeNode* root_;
    int maxlayer;
    int numoflastlayer;
};

 

解法二：bfs based

先使用bfs将所有子节点数为0和1的节点存入队列，然后维护这个队列，对头节点是插入新节点的节点，若对头节点只有右子树为NULL，那么插入后将其pop，并将其两个子节点指针压入队列。

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_;
    }
};