LeetCode·每日一题·919.完全二叉树插入器·层次遍历·BFS
2023-09-27 14:26:29 时间
链接: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)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
时间空间复杂度
相关文章
- 【LeetCode-面试算法经典-Java实现】【075-Sort Colors (颜色排序)】
- 【Leetcode】110. 平衡二叉树(简单)
- 【Leetcode】102. 二叉树的层序遍历(中等)
- JS Leetcode 264. 丑数 II 题解分析,当暴力无法暴力,让我们弃武从文了解三指针
- [LeetCode] Reverse Linked List II
- LeetCode 144. 二叉树的前序遍历
- 112、【树与二叉树】leetcode ——108. 将有序数组转换为二叉搜索树:二分查找树(C++版本)
- 97、【树与二叉树】leetcode ——513.找树左下角的值:层次遍历+回溯法(C++版本)
- 91、【树与二叉树】leetcode ——559.n叉树的最大深度(递归DFS+迭代BFS)(C++版本)
- [LeetCode] 968. Binary Tree Cameras 二叉树相机
- [LeetCode] 1028. Recover a Tree From Preorder Traversal 从先序遍历还原二叉树
- [LeetCode] Closest Leaf in a Binary Tree 二叉树中最近的叶结点
- [LeetCode] Second Minimum Node In a Binary Tree 二叉树中第二小的结点
- [LeetCode] 314. Binary Tree Vertical Order Traversal 二叉树的竖直遍历
- [LeetCode] 103. Binary Tree Zigzag Level Order Traversal 二叉树的之字形层序遍历
- [LeetCode] 105. Construct Binary Tree from Preorder and Inorder Traversal 由先序和中序遍历建立二叉树
- [LeetCode] 106. Construct Binary Tree from Inorder and Postorder Traversal 由中序和后序遍历建立二叉树
- [LeetCode] 145. Binary Tree Postorder Traversal 二叉树的后序遍历
- [LeetCode] 102. Binary Tree Level Order Traversal 二叉树层序遍历
- LeetCode二叉树中序遍历
- leetcode 94. Binary Tree Inorder Traversal 二叉树的中序遍历(中等)
- leetcode 106. Construct Binary Tree from Inorder and Postorder Traversal 从中序与后序遍历序列构造二叉树(中等)
- leetcode 105. Construct Binary Tree from Preorder and Inorder Traversal 从前序与中序遍历序列构造二叉树(中等)
- leetcode 637. Average of Levels in Binary Tree 二叉树的层平均值(简单)