leetcode_919. Complete Binary Tree Inserter

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

leetcode_919. Complete Binary Tree Inserter

 

解法二: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_; } };

 leetcode_919. Complete Binary Tree Inserter

 

上一篇:CF715E Complete the Permutations(计数,斯特林数)


下一篇:docker下载镜像received unexpected Http status:500 Internal Server Error