Class, leetcode919 -- complete binary tree inserter

Topic content

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

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/complete-binary-tree-inserter
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Their thinking

In fact, if you say the meaning of this topic , In fact, it's easy to understand , Is a complete binary tree + The problem of nodes , But one of the trouble is the construction of binary tree , They provided a binary tree , But when I first understood the function of initialization function, there was a deviation , I think we should build a complete binary tree by ourselves , I tried to achieve this , The effect is not good .
After reading the idea of the problem solution, I realized that the function of the initialization function actually has no clear restrictions , It's just for the later functions . As long as all leaf nodes and a possible node with only left node but no right node are stored in the queue during initialization . Then go to an out connection, which is the insertion of binary tree . As for returning to the parent node , The process of finding the node is output .
This is the first question that I do this kind of multiple function types on the force buckle , I still feel a little unnatural , I hope it will be better after more practice , Just like yesterday's weekly race , Encounter the problem of writing classes by multiple functions , I can't start because of lack of experience , So I still have to step up my practice .

Implementation code

/** * 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 {
    
private:
    TreeNode* node;
    queue<TreeNode*> link;

public:
    CBTInserter(TreeNode* root) {
    
        node=root;
        queue<TreeNode*> q;
        if(!root){
    
            node=nullptr;
        }
        q.push(root);
        while(!q.empty()){
    
            TreeNode* dian=q.front();
            q.pop();
            if(dian->left){
    
                q.push(dian->left);
            }
            if(dian->right){
    
                q.push(dian->right);
            }
            if(!dian->left||!dian->right){
    
                link.push(dian);
            }  
        }
    }
    
    int insert(int val) {
    
        TreeNode* dian=new TreeNode(val);
        TreeNode* mid=link.front();
        if(mid->left){
    
            mid->right=dian;
            link.pop();
            link.push(dian);
        }
        else{
    
            mid->left=dian;
            link.push(dian);
        }
        return mid->val;
    }
    
    TreeNode* get_root() {
    
        return node;
    }
};

/** * Your CBTInserter object will be instantiated and called as such: * CBTInserter* obj = new CBTInserter(root); * int param_1 = obj->insert(val); * TreeNode* param_2 = obj->get_root(); */