二叉树题目:完全二叉树插入器
文章目录
- 题目
- 标题和出处
- 难度
- 题目描述
- 要求
- 示例
- 数据范围
- 解法
- 思路和算法
- 代码
- 复杂度分析
题目
标题和出处
标题:完全二叉树插入器
出处: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 插件的应用,以及如何通过引入随机性…...
挑战杯推荐项目
“人工智能”创意赛 - 智能艺术创作助手:借助大模型技术,开发能根据用户输入的主题、风格等要求,生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用,帮助艺术家和创意爱好者激发创意、提高创作效率。 - 个性化梦境…...

【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)
HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

简易版抽奖活动的设计技术方案
1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...
postgresql|数据库|只读用户的创建和删除(备忘)
CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...
OkHttp 中实现断点续传 demo
在 OkHttp 中实现断点续传主要通过以下步骤完成,核心是利用 HTTP 协议的 Range 请求头指定下载范围: 实现原理 Range 请求头:向服务器请求文件的特定字节范围(如 Range: bytes1024-) 本地文件记录:保存已…...
【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】
1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件(System Property Definition File),用于声明和管理 Bluetooth 模块相…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...

04-初识css
一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战
“🤖手搓TuyaAI语音指令 😍秒变表情包大师,让萌系Otto机器人🔥玩出智能新花样!开整!” 🤖 Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制(TuyaAI…...