leetcode_919. Complete Binary Tree Inserter

发布时间：2020-12-14 04:36:16 所属栏目：大数据来源：网络整理

导读：https://leetcode.com/problems/complete-binary-tree-inserter/ 设计一个CBTInserter，使用给定完全二叉树初始化。三个功能; C BTInserter(TreeNode root) ?initializes the data structure on a given tree?with head node? root ; CBTInserter.insert(int

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,insertlayer);
            return res;
        }
        return NULL;
    }
    int insert(int v){int maxnumoflastlayer = pow(2,maxlayer);
        TreeNode* res = NULL;
        if(numoflastlayer<maxnumoflastlayer){
            res = Insert(root_,0,maxlayer);
            numoflastlayer++;
        }else{
            res = Insert(root_,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_;
    }
};

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!