面试算法43:在完全二叉树中添加节点
题目
在完全二叉树中,除最后一层之外其他层的节点都是满的(第n层有2n-1个节点)。最后一层的节点可能不满,该层所有的节点尽可能向左边靠拢。例如,图7.3中的4棵二叉树均为完全二叉树。实现数据结构CBTInserter有如下3种方法。
- 构造函数CBTInserter(TreeNode root),用一棵完全二叉树的根节点初始化该数据结构。
- 函数insert(int v)在完全二叉树中添加一个值为v的节点,并返回被插入节点的父节点。例如,在如图7.3(a)所示的完全二叉树中添加一个值为7的节点之后,二叉树如图7.3(b)所示,并返回节点3。在如图7.3(b)所示的完全二叉树中添加一个值为8的节点之后,二叉树如图7.3(c)所示,并返回节点4。在如图7.3(c)所示的完全二叉树中添加节点9会得到如图7.3(d)所示的二叉树并返回节点4。
- 函数get_root()返回完全二叉树的根节点。

分析
在完全二叉树中添加新节点顺序看起来是从上到下按层从左到右添加的,这就是典型的二叉树广度优先搜索的顺序。我们可以每次在完全二叉树中按照广度优先搜索的顺序找出第1个左子节点或右子节点还有空缺的节点。如果它没有左子节点,那么新的节点就作为它的左子节点;如果它没有右子节点,那么新的节点就作为它的右子节点。
接下来考虑效率优化。在完全二叉树中添加节点时需要按照广度优先搜索的顺序找出第1个缺少子节点的节点。其实没有必要在每次插入新的节点时都从完全二叉树的根节点开始从头进行广度优先搜索。
例如,在如图7.3(a)所示的完全二叉树中添加新的节点7时,从根节点开始按照广度优先搜索的顺序找出节点3是第1个缺少子节点的节点,由此可知,在节点3之前被遍历过的所有节点(节点1和节点2)的左右子节点都已经存在,并且当节点7插入节点3的右子节点的位置之后节点3的左右子节点都已经存在。下次再次插入新的节点时,就没有必要从根节点开始,而是跳过节点1、节点2和节点3,直接从节点4开始查找第1个还缺少子节点的节点。
解
public class CBTInserter {private Queue<TreeNode> queue;private TreeNode root;public CBTInserter(TreeNode root) {this.root = root;queue = new LinkedList<>();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 v) {TreeNode parent = queue.peek();TreeNode node = new TreeNode(v);if (parent.left == null) {parent.left = node;}else {parent.right = node;queue.poll();queue.offer(parent.left);queue.offer(parent.right);}return parent.val;}public TreeNode getRoot() {return this.root;}
}
相关文章:
面试算法43:在完全二叉树中添加节点
题目 在完全二叉树中,除最后一层之外其他层的节点都是满的(第n层有2n-1个节点)。最后一层的节点可能不满,该层所有的节点尽可能向左边靠拢。例如,图7.3中的4棵二叉树均为完全二叉树。实现数据结构CBTInserter有如下3种…...
Python算法例3 检测2的幂次
1. 问题描述 检测一个整数n是否为2的幂次。 2. 问题示例 n8,返回True;n6,返回False。 3.代码实现 # 采用UTF-8编码格式 # 参数n是一个整数 # 返回True或者False class Solution:def checkPowerOf2(self,n):ans 1for i in range(31):if …...
线扫相机DALSA--采集卡Base模式设置
采集卡默认加载“1 X Full Camera Link”固件,Base模式首先要将固件更新为“2 X Base Camera Link”。 右键SCI图标,选择“打开文件所在的位置”,找到并打开SciDalsaConfig的Demo,如上图所示: 左键单击“获取相机”&a…...
Gitee 发行版
Gitee 发行版 1、Gitee 发行版管理2、项目仓库中创建发行版本3、项目中导入3.1 gradle配置3.2 dependencies执行正常,包没有下载 1、Gitee 发行版管理 Gitee 发行版(Release)管理 2、项目仓库中创建发行版本 按照Gitee官网操作就行 3、项目…...
python面向对象
用animal举例代码如下: class Animal:name age 0def call(self):print(I am %s, and I\m %d years old. % (self.name, self.age))def isMe(self, name) -> bool:return self.name nameanimal Animal() animal.name coco animal.age 10 animal.call()prin…...
Go基础——数组、切片、集合
目录 1、数组2、切片3、集合4、范围(range) 1、数组 数组是具有相同唯一类型的一组已编号且长度固定的数据项序列,这种类型可以是任意的原始类型例如整型、字符串或者自定义类型。 Go 语言数组声明需要指定元素类型及元素个数,与…...
Error: no matching distribution found for tensorflow-cpu==2.6.*
目录 install_tensorflow()安装过程中遇到的问题 查找解决方案过程中: 解决办法: install_tensorflow()安装过程中遇到的问题 在服务器上安装tensorflow时,遇到了一个报错信息: 在网上找到一个类似的错误(TensorFlow…...
nginx 进程模型
文章目录 nginx运行模式与进程模式进程模式流程图默认初始化运行模式与进程模式(宏展开)cpu_affinity多CPU绑定合理性判定Nginx的daemon创建(os/unix/ngx_daemon.c)运行模式、进程模式启动 多进程模式下master处理流程设置进程信号、初始化信号掩码、屏蔽…...
TypeScript - 枚举类型 -字符型枚举
什么是枚举 枚举就是有固定的元素的一个对象。 对象的元素可以直接列举出来。 什么是字符型枚举 字符型枚举,就是元素的值是字符串。 就这么简单。 定义一个我看看 来,让我们实际看一下字符型的枚举。 // 定义字符型枚举 enum COLOR2{RED red,BLUE blu…...
分布式锁-Redis红锁解决方案
一 分布式锁的概念 1:概念 分布式锁(多服务共享锁) 在分布式的部署环境下,通过锁机制来让多客户端互斥的对共享资源进行访问控制分布式系统不同进程共同访问共享资源的一种锁的实现。如果不同的系统或同一个系统的不同主机之间共…...
【Ubuntu 终端终结者Ctrl shift e无法垂直分页解决办法】
Ubuntu 终端终结者Ctrl shift e无法垂直分页解决办法 错误原因解决办法 错误原因 这是因为ibus输入法有一个快捷键占用了这个终端终结者的快捷键 解决办法 打开命令行输入 ibus-setup进入到如下页面随后将其中的表情注释的快捷键删除即可...
Error: error:0308010C:digital envelope routines::unsupported
Error: error:0308010C:digital envelope routines::unsupported 问题描述: 使用 npm run dev 或者 yarn run dev 时 报错:Error: error:0308010C:digital envelope routines::unsupported PS D:\Project\dlspeed_all\GS-IMS\ruoyi-ui> npm run de…...
RTMP在智能眼镜行业应用方案有哪些?
方案示例 视频直播:智能眼镜通常具有摄像头和显示屏,可以实时拍摄和显示视频。RTMP协议可以用于将智能眼镜拍摄的视频传输到服务器,以便其他用户可以实时观看。远程协作:智能眼镜可以用于远程协作,例如在医疗、建筑等…...
【每日一题】合并两个有序数组
链接奉上:合并两个有序数组 目录 直接合并后排序:思路:代码实现: 双指针思路:代码实现: 直接合并后排序: 思路: 将nums2直接合并到nums1后边,并进行排序 代码实现&…...
MySQL---表的增查改删(CRUD进阶)
文章目录 数据库约束表的设计一对一一对多多对多 新增查询聚合查询分组查询联合查询内连接外连接自连接子查询合并查询 数据库约束 数据库约束就是指:程序员定义一些规则对数据库中的数据进行限制。这样数据库会在新增和修改数据的时候按照这些限制,对数…...
《HelloGitHub》第 91 期
兴趣是最好的老师,HelloGitHub 让你对编程感兴趣! 简介 HelloGitHub 分享 GitHub 上有趣、入门级的开源项目。 github.com/521xueweihan/HelloGitHub 这里有实战项目、入门教程、黑科技、开源书籍、大厂开源项目等,涵盖多种编程语言 Python、…...
jvm线上异常排查流程
1. Linux命令 jps 找出当前运行实例 2. jinfo -flags pid(java运行id) 打印出当前设置的jvm内存参数情况 3.jstat -gcutil pid 1000 10 每秒打印一次当前jvm的gc运行情况,一共打印10次 4.将gc日志下载进行分析:到底是因为什么原因导致一直…...
python项目之酒店客房入侵检测系统的设计与实现
项目简介 酒店客房入侵检测系统的设计与实现实现了以下功能: 1、控制台: 控制台是整个系统的首页面。在控制台中,酒店的客房管理人员能够在该页面中查看到当前的空余客房数量、当前在店的客房人数、当前的已用客房数量、当前酒店全部的客房…...
C++ 学习系列 -- 标准库常用得 algorithm function
一 前言 c 标准库中提供了许多操作数据结构:vector、list、deque、map、set 等函数,学习并了解这些常用函数对于我们理解 c 的一些设计模式有着重要的作用。 二 常用的 algorithm function 源码 源代码位置: bits/stl_algo.h 1. accumu…...
[论文笔记]E5
引言 今天又带来一篇文本匹配/文本嵌入的笔记:Text Embeddings by Weakly-Supervised Contrastive Pre-training。中文题目是 基于弱监督对比预训练计算文本嵌入。 本篇工作提出了E5模型(EmbEddings from bidirEctional Encoder rEpresentations)。该模型以带弱监督信号的对…...
系统设计 --- MongoDB亿级数据查询优化策略
系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log,共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题,不能使用ELK只能使用…...
【算法训练营Day07】字符串part1
文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接:344. 反转字符串 双指针法,两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...
【2025年】解决Burpsuite抓不到https包的问题
环境:windows11 burpsuite:2025.5 在抓取https网站时,burpsuite抓取不到https数据包,只显示: 解决该问题只需如下三个步骤: 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...
面向无人机海岸带生态系统监测的语义分割基准数据集
描述:海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而,目前该领域仍面临一个挑战,即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...
uniapp 开发ios, xcode 提交app store connect 和 testflight内测
uniapp 中配置 配置manifest 文档:manifest.json 应用配置 | uni-app官网 hbuilderx中本地打包 下载IOS最新SDK 开发环境 | uni小程序SDK hbulderx 版本号:4.66 对应的sdk版本 4.66 两者必须一致 本地打包的资源导入到SDK 导入资源 | uni小程序SDK …...
Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)
引言 工欲善其事,必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后,我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集,就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...
论文阅读笔记——Muffin: Testing Deep Learning Libraries via Neural Architecture Fuzzing
Muffin 论文 现有方法 CRADLE 和 LEMON,依赖模型推理阶段输出进行差分测试,但在训练阶段是不可行的,因为训练阶段直到最后才有固定输出,中间过程是不断变化的。API 库覆盖低,因为各个 API 都是在各种具体场景下使用。…...
6️⃣Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙
Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙 一、前言:离区块链还有多远? 区块链听起来可能遥不可及,似乎是只有密码学专家和资深工程师才能涉足的领域。但事实上,构建一个区块链的核心并不复杂,尤其当你已经掌握了一门系统编程语言,比如 Go。 要真正理解区…...
Spring AOP代理对象生成原理
代理对象生成的关键类是【AnnotationAwareAspectJAutoProxyCreator】,这个类继承了【BeanPostProcessor】是一个后置处理器 在bean对象生命周期中初始化时执行【org.springframework.beans.factory.config.BeanPostProcessor#postProcessAfterInitialization】方法时…...
【1】跨越技术栈鸿沟:字节跳动开源TRAE AI编程IDE的实战体验
2024年初,人工智能编程工具领域发生了一次静默的变革。当字节跳动宣布退出其TRAE项目(一款融合大型语言模型能力的云端AI编程IDE)时,技术社区曾短暂叹息。然而这一退场并非终点——通过开源社区的接力,TRAE在WayToAGI等…...
