Leetcode-919: complete binary tree inserter

subject

Topic linking

Perfect binary tree Every floor （ Except for the last floor ） All completely filled （ namely , The number of nodes reaches the maximum ） Of , And all nodes are concentrated on the left as much as possible .

Design an algorithm , Insert a new node into a complete binary tree , And keep it intact after insertion .

Realization CBTInserter class :

CBTInserter(TreeNode root) Use the header node as root Initialize the data structure for the given tree ;
CBTInserter.insert(int v) Insert a value of... Into the tree Node.val == val The new node TreeNode. Keep the tree in the state of a complete binary tree , And return to the insert node TreeNode The value of the parent node of ;
CBTInserter.get_root() The head node of the tree will be returned .

Example 1：

 Input 
["CBTInserter", "insert", "insert", "get_root"]
[[[1, 2]], [3], [4], []]
 Output 
[null, 1, 2, [1, 2, 3, 4]]

 explain 
CBTInserter cBTInserter = new CBTInserter([1, 2]);
cBTInserter.insert(3);  //  return  1
cBTInserter.insert(4);  //  return  2
cBTInserter.get_root(); //  return  [1, 2, 3, 4]

Problem solving

Method 1 ： Double queue —O(1) Complexity insertion

If you perform sequence traversal every time you insert , Then if there are many inserts , It's going to be inefficient .
If you can take nodes directly from the queue , Then insert , Then it will be much faster .

Because it's a perfect binary tree , The inserted node , Can only be 2 States

1. No left 、 The right child node , In this case, the left node is inserted first
2. There are left child nodes , No right child node , In this case , Insert the right node

During initialization, the situation 1, Stored in q_L In line , Put the situation 2, Stored in q_R In line .

Therefore, sequence traversal , initialization q_L,q_R queue
Due to the characteristics of complete binary tree , When inserting , Priority from q_R Value in queue .

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
class CBTInserter {
    
public:
    TreeNode* root;
    queue<TreeNode*> q_L;// Store nodes without left and right children 
    queue<TreeNode*> q_R;// Store nodes without right children 

    CBTInserter(TreeNode* root) {
    // The purpose is to initialize q_L and q_R queue 
        this->root=root;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
    
            TreeNode* cur=q.front();
            q.pop();
            if(!cur->left&&!cur->right) q_L.push(cur);
            if(cur->left&&!cur->right) q_R.push(cur);

            if(cur->left) q.push(cur->left);
            if(cur->right) q.push(cur->right);
        }
    }
    
    int insert(int val) {
    
        if(!q_R.empty()){
    // Take the node without right child first ( Because of the characteristics of complete binary tree )
            TreeNode* cur=q_R.front();
            q_R.pop();
            cur->right=new TreeNode(val);
            q_L.push(cur->right);
            return cur->val;
        }
        else{
    // Take nodes without left and right children 
            TreeNode* cur=q_L.front();
            q_L.pop();
            cur->left=new TreeNode(val);
            q_R.push(cur);
            q_L.push(cur->left);
            return cur->val;
        }
    }

    
    TreeNode* get_root() {
    
        return root;
    }
};

Method 2 ： Insertion time – Sequence traversal

class CBTInserter {
    
public:
    TreeNode* root;
    CBTInserter(TreeNode* root) {
    
        this->root=root;
    }
    
    int insert(int val) {
    
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
    
            TreeNode* cur=q.front();
            q.pop();
            if(cur->left) q.push(cur->left);
            else{
    
                cur->left=new TreeNode(val);
                return cur->val;
            }
            if(cur->right) q.push(cur->right);
            else{
    
                cur->right=new TreeNode(val);
                return cur->val;
            }
        }
        return -1;
    }
    
    TreeNode* get_root() {
    
        return root;
    }
};