二叉树题目:完全二叉树插入器
文章目录
- 题目
- 标题和出处
- 难度
- 题目描述
- 要求
- 示例
- 数据范围
- 解法
- 思路和算法
- 代码
- 复杂度分析
题目
标题和出处
标题:完全二叉树插入器
出处:919. 完全二叉树插入器
难度
6 级
题目描述
要求
完全二叉树是每一层(除最后一层外)都是完全填充的,并且所有的结点都尽可能地集中在左侧。
设计一种算法,将一个新结点插入到一个完全二叉树中,并在插入后保持完全二叉树。
实现 CBTInserter \texttt{CBTInserter} CBTInserter 类:
- CBTInserter(TreeNode root) \texttt{CBTInserter(TreeNode root)} CBTInserter(TreeNode root) 使用完全二叉树的根结点 root \texttt{root} root 初始化数据结构;
- int insert(int v) \texttt{int insert(int v)} int insert(int v) 向树中插入一个值为 val \texttt{val} val 的新结点,使树保持完全二叉树的状态,并返回插入结点的父结点的值;
- TreeNode get_root() \texttt{TreeNode get\_root()} TreeNode get_root() 返回树的头结点。
示例
示例 1:
输入:
["CBTInserter", "insert", "insert", "get_root"] \texttt{["CBTInserter", "insert", "insert", "get\_root"]} ["CBTInserter", "insert", "insert", "get_root"]
[[[1, 2]], [3], [4], []] \texttt{[[[1, 2]], [3], [4], []]} [[[1, 2]], [3], [4], []]
输出:
[null, 1, 2, [1, 2, 3, 4]] \texttt{[null, 1, 2, [1, 2, 3, 4]]} [null, 1, 2, [1, 2, 3, 4]]
解释:
CBTInserter cBTInserter = new CBTInserter([1, 2]); \texttt{CBTInserter cBTInserter = new CBTInserter([1, 2]);} CBTInserter cBTInserter = new CBTInserter([1, 2]);
cBTInserter.insert(3); \texttt{cBTInserter.insert(3);} cBTInserter.insert(3); // 返回 1 \texttt{1} 1
cBTInserter.insert(4); \texttt{cBTInserter.insert(4);} cBTInserter.insert(4); // 返回 2 \texttt{2} 2
cBTInserter.get_root(); \texttt{cBTInserter.get\_root();} cBTInserter.get_root(); // 返回 [1, 2, 3, 4] \texttt{[1, 2, 3, 4]} [1, 2, 3, 4]
数据范围
- 树中结点数目在范围 [1, 1000] \texttt{[1, 1000]} [1, 1000] 内
- 0 ≤ Node.val ≤ 5000 \texttt{0} \le \texttt{Node.val} \le \texttt{5000} 0≤Node.val≤5000
- root \texttt{root} root 是完全二叉树
- 0 ≤ val ≤ 5000 \texttt{0} \le \texttt{val} \le \texttt{5000} 0≤val≤5000
- 最多调用 10 4 \texttt{10}^\texttt{4} 104 次 insert \texttt{insert} insert 和 get_root \texttt{get\_root} get_root
解法
思路和算法
这道题的解法不唯一。一种常规的解法是维护完全二叉树中的结点数,每次插入结点时根据结点数定位到插入结点的位置。当完全二叉树中有 n n n 个结点时,该解法每次插入操作的时间复杂度是 O ( log n ) O(\log n) O(logn)。
利用完全二叉树的性质,可以将每次插入操作的时间复杂度降低到 O ( 1 ) O(1) O(1)。
由于完全二叉树的结点插入顺序和层序遍历相同,因此在初始化时可以使用层序遍历访问完全二叉树中的每个结点。每次插入的结点的父结点一定是层序遍历访问到的第一个存在空子结点的结点,父结点满足两个子结点都为空或者只有右子结点为空。如果父结点的两个子结点都为空,则插入的结点作为父结点的左子结点;如果父结点的子结点中只有右子结点为空,则插入的结点作为父结点的右子结点。
如果一个结点的两个子结点都不为空,则下一个插入的结点的父结点一定是层序遍历顺序中当前结点后面的结点。因此,维护完全二叉树的根结点和队列,即可实现每次插入使用 O ( 1 ) O(1) O(1) 的时间完成。
初始化时将根结点入队列,然后执行如下操作:如果队首结点的两个子结点都不为空,则将队首结点出队列,并将队首结点的左子结点和右子结点依次入队列。重复该操作直到队首结点的两个子结点中至少有一个为空。
对于插入结点操作,使用给定的结点值创建新结点,此时队首结点即为插入结点的父结点。执行如下操作。
-
判断父结点的左子结点是否为空,执行相应的操作。
-
如果父结点的左子结点为空,则将新结点作为父结点的左子结点。
-
如果父结点的左子结点不为空,则将新结点作为父结点的右子结点,然后将父结点出队列,并将父结点的左子结点和右子结点依次入队列。
-
-
返回父结点值。
对于返回根结点操作,返回完全二叉树的根结点即可。
代码
class CBTInserter {TreeNode root;Queue<TreeNode> queue;public CBTInserter(TreeNode root) {this.root = root;queue = new ArrayDeque<TreeNode>();queue.offer(root);while (queue.peek().left != null && queue.peek().right != null) {TreeNode node = queue.poll();queue.offer(node.left);queue.offer(node.right);}}public int insert(int val) {TreeNode insertNode = new TreeNode(val);TreeNode node = queue.peek();if (node.left == null) {node.left = insertNode;} else {node.right = insertNode;queue.poll();queue.offer(node.left);queue.offer(node.right);}return node.val;}public TreeNode get_root() {return root;}
}
复杂度分析
-
时间复杂度:构造方法的时间复杂度是 O ( n ) O(n) O(n),插入结点操作和返回根结点操作的时间复杂度都是 O ( 1 ) O(1) O(1),其中 n n n 是二叉树的结点数。构造方法需要对完全二叉树层序遍历,需要 O ( n ) O(n) O(n) 的时间。插入结点操作将新结点作为父结点的子结点,可能有队列操作,需要 O ( 1 ) O(1) O(1) 的时间。返回根结点操作直接返回完全二叉树的根结点,需要 O ( 1 ) O(1) O(1) 的时间。
-
空间复杂度: O ( n ) O(n) O(n),其中 n n n 是二叉树的结点数。需要存储完全二叉树以及使用队列存储完全二叉树中的子结点不完全的结点。
相关文章:

二叉树题目:完全二叉树插入器
文章目录 题目标题和出处难度题目描述要求示例数据范围 解法思路和算法代码复杂度分析 题目 标题和出处 标题:完全二叉树插入器 出处:919. 完全二叉树插入器 难度 6 级 题目描述 要求 完全二叉树是每一层(除最后一层外)都…...

用MATLAB求最短路径(graphshortestpath)和求最小生成树(minspantree),代码演示
求最短路径(graphshortestpath),求最小生成树(minspantree) 文章目录 求最短路径(graphshortestpath),求最小生成树(minspantree)1、最短路径问题2、最小生成…...

用win系统搭建Minecraft世界服务器,MC开服教程,小白开服教程
雨云VPS用Windows系统搭建我的世界世界服务器,Minecraft开服教程,小白开服教程,MC 1.19.4版本服务器搭建教程。 此教程使用 Mohist 1.19.4 服务端,此服务端支持Forge模组和Bukkit/Spigot/Paper插件,如果需要开其他服务…...

MacOS安装Miniforge、Tensorflow、Jupyter Lab等(2024年最新)
大家好,我是邵奈一,一个不务正业的程序猿、正儿八经的斜杠青年。 1、世人称我为:被代码耽误的诗人、没天赋的书法家、五音不全的歌手、专业跑龙套演员、不合格的运动员… 2、这几年,我整理了很多IT技术相关的教程给大家࿰…...

iOS 应用上架指南:资料填写及提交审核
摘要 本文提供了iOS新站上架资料填写及提交审核的详细指南,包括创建应用、资料填写-综合、资料填写-IOS App和提交审核等步骤。通过本指南,您将了解到如何填写正确的资料,并顺利通过苹果公司的审核。 引言 在开发iOS应用后,将其…...

车速预测 | Matlab基于RBF径向基神经网络的车速预测模型(多步预测,尾巴图)
目录 效果一览基本介绍程序设计参考资料 效果一览 基本介绍 车速预测 | Matlab基于RBF径向基神经网络的车速预测模型(多步预测,尾巴图) 程序设计 完整程序和数据获取方式:私信博主回复Matlab基于RBF径向基神经网络的车速预测模型…...

MySQL 5.7.35下载安装使用_忘记密码_远程授权
文章目录 MySQL 5.7.35下载安装使用_忘记密码_远程授权MySQL下载地址mysql安装点击安装,最好以管理员身份运行选择自定义安装选择64位勾选启动自定义产品执行点击同意点击下一步点击执行下一步配置数据库端口号设置登录密码,如果密码忘记,下面…...

openGauss学习笔记-194 openGauss 数据库运维-常见故障定位案例-分析查询语句长时间运行的问题
文章目录 openGauss学习笔记-194 openGauss 数据库运维-常见故障定位案例-分析查询语句长时间运行的问题194.1 分析查询语句长时间运行的问题194.1.1 问题现象194.1.2 原因分析194.1.3 处理办法 openGauss学习笔记-194 openGauss 数据库运维-常见故障定位案例-分析查询语句长时…...

GoLang:gRPC协议的介绍以及详细教程,从Protocol开始
目录 编辑 引言 一、安装相关Go语言库和相关工具 1. 安装Go 2. 安装Protocol Buffers Compiler 2.1 Windows 2.1.1 下载 2.1.2 解压 2.1.3 环境变量 2. macOS 3. Linux 4. 验证安装 3. 安装gRPC-Go 4. 安装Protocol Buffers的Go插件 二、定义服务 三、生成Go…...
LeetCode-2645. 构造有效字符串的最少插入数
给你一个字符串 word ,你可以向其中任何位置插入 “a”、“b” 或 “c” 任意次,返回使 word 有效需要插入的最少字母数。 如果字符串可以由 “abc” 串联多次得到,则认为该字符串有效 。 示例 1: 输入:word “b” …...

ssm+vue的城投公司企业人事管理系统设计与实现(有报告)。Javaee项目,ssm vue前后端分离项目。
演示视频: ssmvue的城投公司企业人事管理系统设计与实现(有报告)。Javaee项目,ssm vue前后端分离项目。 项目介绍: 采用M(model)V(view)C(controller&#x…...

nginx基础面试题以及配置文件解析和命令控制
目录 1、nginx是什么 2、nginx的特点 3、为什么中国大陆有:百度、京东、新浪、网易、腾讯、淘宝等这么多用户使用nginx 4、nginx 的内部技术架构 上一期我们配置安装了nginx接着讲一下nginx配置文件的解析和nginx 命令控制 感谢观看!希望能够帮助到…...

全自动网页生成系统网站源码重构版
源码优点: 所有模板经过精心审核与修改,完美兼容小屏手机大屏手机,以及各种平板端、电脑端和360浏览器、谷歌浏览器、火狐浏览器等等各大浏览器显示。 免费制作 为用户使用方便考虑,全自动网页制作系统无需繁琐的注册与登入,直…...

【算法每日一练]-动态规划 (保姆级教程 篇16) #纸带 #围栏木桩 #四柱河内塔
目录 今日知识点: 计算最长子序列的方案个数,类似最短路径个数问题 四柱河内塔问题:dp[i]min{ (p[i-k]f[k])dp[i-k] } 纸带 围栏木桩 四柱河内塔 纸带 思路: 我们先设置dp[i]表示从i到n的方案数。 那么减法操作中ÿ…...

Grounding 模型 + SAM 报错
引入 Grounding 目标检测模型串联 SAM 从而实现实例分割任务,目前支持 Grounding DINO 和 GLIP 参考教程 MMDetection-SAM 如果是 Grounding DINO 则安装如下依赖即可 cd playground pip install githttps://github.com/facebookresearch/segment-anything.git pip…...

linux 网络基础配置
将Linux主机接入到网络,需要配置网络相关设置一般包括如下内容: 主机名 iP/netmask (ip地址,网关) 路由:默认网关 网络连接状态 DNS服务器 (主DNS服务器 次DNS服务器 第三个DNS服务器) 一、…...
leetcode-相同的树
100. 相同的树 使用递归的方法 # Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution:def isSameTree(self, p: …...
Leetcode17-好数对的数目(1512)
1、题目 给你一个整数数组 nums 。 如果一组数字 (i,j) 满足 nums[i] nums[j] 且 i < j ,就可以认为这是一组 好数对 。 返回好数对的数目。 示例 1: 输入:nums [1,2,3,1,1,3] 输出:4 解释:有 4 组好数对&am…...

Ubuntu22.04开机左上角下划线闪烁不开机
按下CtrlAltF2,打开TTY系统,然后通过用户名和密码登录,随后使用 sudo apt --fix-broken install 根据提示排除错误信息,然后使用apt安装lightdm安装就行。 tips:当使用EasyConnect的时候,你可能参考了下面这篇文章知…...

提升测试多样性,揭秘Pytest插件pytest-randomly
大家可能知道在Pytest测试生态中,插件扮演着不可或缺的角色,为开发者提供了丰富的功能和工具。其中,pytest-randomly 插件以其能够引入随机性的特性而备受欢迎。本文将深入探讨 pytest-randomly 插件的应用,以及如何通过引入随机性…...
<6>-MySQL表的增删查改
目录 一,create(创建表) 二,retrieve(查询表) 1,select列 2,where条件 三,update(更新表) 四,delete(删除表…...
IGP(Interior Gateway Protocol,内部网关协议)
IGP(Interior Gateway Protocol,内部网关协议) 是一种用于在一个自治系统(AS)内部传递路由信息的路由协议,主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力
引言: 在人工智能快速发展的浪潮中,快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型(LLM)。该模型代表着该领域的重大突破,通过独特方式融合思考与非思考…...
使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装
以下是基于 vant-ui(适配 Vue2 版本 )实现截图中照片上传预览、删除功能,并封装成可复用组件的完整代码,包含样式和逻辑实现,可直接在 Vue2 项目中使用: 1. 封装的图片上传组件 ImageUploader.vue <te…...
C++中string流知识详解和示例
一、概览与类体系 C 提供三种基于内存字符串的流,定义在 <sstream> 中: std::istringstream:输入流,从已有字符串中读取并解析。std::ostringstream:输出流,向内部缓冲区写入内容,最终取…...
【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)
升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点,但无自动故障转移能力,Master宕机后需人工切换,期间消息可能无法读取。Slave仅存储数据,无法主动升级为Master响应请求ÿ…...
爬虫基础学习day2
# 爬虫设计领域 工商:企查查、天眼查短视频:抖音、快手、西瓜 ---> 飞瓜电商:京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空:抓取所有航空公司价格 ---> 去哪儿自媒体:采集自媒体数据进…...

自然语言处理——循环神经网络
自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元(GRU)长短期记忆神经网络(LSTM)…...
什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南
文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果
均衡后的SNRSINR
本文主要摘自参考文献中的前两篇,相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程,其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt 根发送天线, n r n_r nr 根接收天线的 MIMO 系…...