Leetcode · daily question · 919. complete binary tree inserter · hierarchy traversal · BFS

link ：https://leetcode.cn/problems/complete-binary-tree-inserter/solution/by-xun-ge-v-anga/
source ： Power button （LeetCode）
The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source . 

subject

Example

Ideas

Their thinking
Breadth first search
The title requires a binary tree , Every time a new node is inserted, the tree must be a complete binary tree

• A complete binary tree is every layer （ 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 .

It's not hard to find out , Actually, the hierarchy of the tree is traversed -> Check each floor Just enough to traverse the tree , Check the insertion point of the complete binary tree , Because every time, all nodes of the first layer are checked, and the priority left side is also met , The tree is traversed hierarchically every time it is inserted , Find the first notch, which is the insertion point

Concrete realization
For hierarchical traversal implementation , There are two ways , The first kind of recursion , The second queue iteration , The title requires us to return to the parent node of the insertion point , But recursion will recursively enter , The parent node is not well preserved , So it is more convenient to use queue iteration
Queue iteration realizes post order traversal
Define a queue , The size is 10000, Because the topic requires to call functions at most 10000 Time , First put the header node into the queue , Then pop up to determine whether there are left and right nodes , Exist and join the team , If it does not exist, you can insert a new node , And return the current node value .

Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */



typedef struct {// initialization 
    struct TreeNode * root;
} CBTInserter;

// initialization 
CBTInserter* cBTInserterCreate(struct TreeNode* root) {
    CBTInserter * obj = malloc(sizeof(CBTInserter));
    obj->root = root;
    return obj;
}
// Iterative implementation of hierarchical traversal 
int cBTInserterInsert(CBTInserter* obj, int val) {
    struct TreeNode * next = obj->root;
    struct TreeNode * res[10000];
    /*struct TreeNode * node = malloc(sizeof(struct TreeNode));// Initialize new insertion point 
    node->val = val;
    node->left = NULL;
    node->right = NULL;*/
    int l = 0;
    int r = 0;
    res[r++] = next;// Head node join the team 
    while(l < r)// Level traversal 
    {
        int rr = r;
        while(l < rr)// Go through each layer 
        {
            if(res[l]->left)// Determine whether the left and right nodes exist 
            {
                res[r++] = res[l]->left;
            }
            else
            {
                struct TreeNode * node = malloc(sizeof(struct TreeNode));// Initialize new insertion point 
                node->val = val;
                node->left = NULL;
                node->right = NULL;
                res[l]->left = node;
                return res[l]->val;
            }
            if(res[l]->right)
            {
                res[r++] = res[l]->right;
            }
            else
            {
                struct TreeNode * node = malloc(sizeof(struct TreeNode));// Initialize new insertion point 
                node->val = val;
                node->left = NULL;
                node->right = NULL;
                res[l]->right = node;
                return res[l]->val;
            }
            l++;
        }
    }
    return -1;
}

struct TreeNode* cBTInserterGet_root(CBTInserter* obj) {
    return obj->root;
}   

void TreeFree(struct TreeNode * root)
{
    if(root == NULL)
    {
        return;
    }
    TreeFree(root->left);
    TreeFree(root->right);
    free(root);
}
void cBTInserterFree(CBTInserter* obj) {// Recursively destroy the tree 
    TreeFree(obj->root);
    free(obj);    
}

/**
 * Your CBTInserter struct will be instantiated and called as such:
 * CBTInserter* obj = cBTInserterCreate(root);
 * int param_1 = cBTInserterInsert(obj, val);
 
 * struct TreeNode* param_2 = cBTInserterGet_root(obj);
 
 * cBTInserterFree(obj);
*/

 author ：xun-ge-v
 link ：https://leetcode.cn/problems/complete-binary-tree-inserter/solution/by-xun-ge-v-anga/
 source ： Power button （LeetCode）
 The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .

Time and space complexity