Leetcode 0919. complete binary tree inserter: array representation of complete binary tree

【LetMeFly】919. Complete binary tree inserter ： Array representation of complete binary tree

Force button topic link ：https://leetcode.cn/problems/complete-binary-tree-inserter/

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]

 

Tips ：

• The number of nodes in the tree ranges from  [1, 1000] 
• 0 <= Node.val <= 5000
• root  It's a perfect binary tree
• 0 <= val <= 5000 
• Each test case calls at most  insert  and  get_root  operation  104  Time

Method 1 ： Use an array to store a complete binary tree

A complete binary tree has the following properties ：

If the root node is from 1 Start numbering in a hierarchical way , that $The\; number\; of\; the\; parent\; node=\lfloor \frac{The\; number\; of\; the\; child\; node}{2}\rfloor$

therefore , We can use arrays to store the nodes of a complete binary tree , So when adding new nodes , Directly append the new node to the end of the array , You can easily get the parent node of the new node $O(1)$.

after , Point the child node of the parent node to the new node .

• Time complexity $O(n)$, among $n$ Is the number of nodes of the initial binary tree
• Spatial complexity $O(m)$, among $m$ Is the number of nodes of the final binary tree

AC Code

C++

class CBTInserter {
    
private:
    vector<TreeNode*> a;
public:
    CBTInserter(TreeNode* root) {
      //  Initial binary tree , Store the array in a hierarchical way 
        queue<TreeNode*> q;
        q.push(root);
        while (q.size()) {
    
            TreeNode* p = q.front();
            q.pop();
            a.push_back(p);
            if (p->left)
                q.push(p->left);
            if (p->right)
                q.push(p->right);
        }
    }
    
    int insert(int val) {
    
        TreeNode* thisNode = new TreeNode(val);  //  New node 
        a.push_back(thisNode);
        int th = a.size();  //  Number of new node 
        TreeNode* father = a[th / 2 - 1];  //  The number of the parent node  =  Number of new node  / 2 ;-1 Because the subscript in the array is from 0 At first, the binary tree node starts from 1 Numbered starting 
        if (th % 2) {
      //  Odd numbers indicate left nodes 
            father->right = thisNode;
        }
        else {
    
            father->left = thisNode;
        }
        return father->val;
    }
    
    TreeNode* get_root() {
    
        return a[0];  //  The root is the first node in the array 
    }
};

Synchronous posting on CSDN, Originality is not easy. , Reprint please attach Link to the original text Oh ~
Tisfy：https://letmefly.blog.csdn.net/article/details/125974862