leetcode_919. Complete Binary Tree Inserter
2024-09-08 08:09:48
https://leetcode.com/problems/complete-binary-tree-inserter/
设计一个CBTInserter，使用给定完全二叉树初始化。三个功能;
CBTInserter(TreeNode root)initializes the data structure on a given tree with head noderoot;CBTInserter.insert(int v)will insert aTreeNodeinto the tree with valuenode.val = vso that the tree remains complete, and returns the value of the parent of the insertedTreeNode;CBTInserter.get_root()will return the head node of the tree.
主要涉及完全二叉树的插入。
解法一：dfs based
对给定的完全二叉树，先计算其最大高度maxlayer，以及深度最深的节点数numoflastlayer。如果numoflastlayer<2^(maxlayer-1)，说明应该在maxlayer-1层第一个子节点数小于2的节点插入；如果numoflastlayer==2^(maxlayer-1)，说明应该在maxlayer层第一个子节点处插入，利用dfs可以完成。插入过后及时更新maxlager和numoflastlayer。
class CBTInserter{
public:
void preorder(TreeNode* root,int layer){
if(layer>maxlayer){
maxlayer = layer;
numoflastlayer = ;
}else if(layer == maxlayer)
numoflastlayer++;
if(root->left!=NULL)
preorder(root->left, layer+);
if(root->right!=NULL)
preorder(root->right, layer+);
}
CBTInserter(TreeNode* root){
root_ =root;
maxlayer=-;
numoflastlayer=;
preorder(root,);
}
TreeNode* Insert(TreeNode* root, int v, int layer, int insertlayer){
if(layer == insertlayer-){
if(root->left == NULL){
root->left = new TreeNode(v);
return root;
}else if(root->right == NULL){
root->right = new TreeNode(v);
return root;
}
}else{
TreeNode* res = Insert(root->left, v, layer+, insertlayer);
if(res == NULL)
res = Insert(root->right, v, layer+, insertlayer);
return res;
}
return NULL;
}
int insert(int v){int maxnumoflastlayer = pow(, maxlayer);
TreeNode* res = NULL;
if(numoflastlayer<maxnumoflastlayer){
res = Insert(root_,v,, maxlayer);
numoflastlayer++;
}else{
res = Insert(root_,v,,maxlayer+);
maxlayer++;
numoflastlayer=;
}
return res->val;
}
TreeNode* get_root(){
return root_;
}
private:
TreeNode* root_;
int maxlayer;
int numoflastlayer;
};
解法二：bfs based
先使用bfs将所有子节点数为0和1的节点存入队列，然后维护这个队列，对头节点是插入新节点的节点，若对头节点只有右子树为NULL，那么插入后将其pop，并将其两个子节点指针压入队列。
class CBTInserter{
public:
TreeNode* root_;
queue<TreeNode*> nodes_0_1;
CBTInserter(TreeNode* root){
root_ = root;
queue<TreeNode*> que;
que.push(root);
while(!que.empty()){
TreeNode* now = que.front();
que.pop();
if(now->left == NULL)
nodes_0_1.push(now);
else if(now->right == NULL)
nodes_0_1.push(now);
else{
que.push(now->left);
que.push(now->right);
}
}
}
int insert(int v){
TreeNode* root = nodes_0_1.front();
if(root->left!=NULL){
root->right = new TreeNode(v);
nodes_0_1.pop();
nodes_0_1.push(root->left);
nodes_0_1.push(root->right);
}
else
root->left = new TreeNode(v);
return root->val;
}
TreeNode* get_root(){
return root_;
}
};
最新文章
- java的三大框架（一）
- html5菜单折纸效果
- Linux用户组与用户组基本命令
- SharedPreferences实现自动登录记住用户名密码
- ArcGIS Engine 几何对象和WKB的转换
- 使用pip install 或者easy_install安装Python的各种包出现cc failed with exit status 1
- robot自动化测试（一）---安装
- Python 用SMTP发送邮件
- 小技巧：Oracle：sqlplus 显示行列字符数
- 学习笔记 intent属性
- ssh密钥登录
- PERL学习笔记---正则表达式
- Kubernetes - 腾讯蓝鲸配置平台(CMDB)开源版部署
- 批量镜像locator（比如表情模板）
- C#中EXCEL表格的内容进度条实现
- sql重复数据的过滤问题
- Git安装学习记录
- 查看linux 内存
- 【读书笔记】Linux内核设计与实现（第十八章）
- PL/SQL如何设置当前格局确保每次打开都给关闭前一样