LeetCode·每日一题·919.完全二叉树插入器·层次遍历·BFS

链接：https://leetcode.cn/problems/complete-binary-tree-inserter/solution/by-xun-ge-v-anga/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 

题目

示例

思路

解题思路
广度优先搜索
题目要求对一个二叉树，每插入一个新节点都需满足树为完全二叉树

• 完全二叉树是每一层（除最后一层外）都是完全填充（即，节点数达到最大）的，并且所有的节点都尽可能地集中在左侧。

不难发现，其实树的层次遍历->检查每一层 正好能满足对树遍历时，检查完全二叉树的插入点，因为每次都是检查一层所有节点同时还满足优先左边，每次插入时对树进行层次遍历，查找第一个缺口即为插入点

具体实现
对于层次遍历实现，有两种方法，第一种递归，第二种队列迭代，题目需要我们返回插入点的父节点，但是递归会递归进入，对于父节点并不是很好保存，所以使用队列迭代更方便
队列迭代实现后序遍历
定义一个队列，大小为10000，因为题目要求最多调用函数10000次，先将头节点存入队列，然后弹出判断是否存在左右节点，存在入队，不存在即可插入新节点，并返回当前节点值。

代码

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



typedef struct {//初始化
    struct TreeNode * root;
} CBTInserter;

//初始化
CBTInserter* cBTInserterCreate(struct TreeNode* root) {
    CBTInserter * obj = malloc(sizeof(CBTInserter));
    obj->root = root;
    return obj;
}
//迭代实现层次遍历
int cBTInserterInsert(CBTInserter* obj, int val) {
    struct TreeNode * next = obj->root;
    struct TreeNode * res[10000];
    /*struct TreeNode * node = malloc(sizeof(struct TreeNode));//初始化新插入点
    node->val = val;
    node->left = NULL;
    node->right = NULL;*/
    int l = 0;
    int r = 0;
    res[r++] = next;//头节点入队
    while(l < r)//层次遍历
    {
        int rr = r;
        while(l < rr)//遍历每一层
        {
            if(res[l]->left)//判断左右节点是否存在
            {
                res[r++] = res[l]->left;
            }
            else
            {
                struct TreeNode * node = malloc(sizeof(struct TreeNode));//初始化新插入点
                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));//初始化新插入点
                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) {//递归销毁树
    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);
*/

作者：xun-ge-v
链接：https://leetcode.cn/problems/complete-binary-tree-inserter/solution/by-xun-ge-v-anga/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时间空间复杂度