当前位置: 首页 > news >正文

面试算法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:在完全二叉树中添加节点

题目 在完全二叉树中&#xff0c;除最后一层之外其他层的节点都是满的&#xff08;第n层有2n-1个节点&#xff09;。最后一层的节点可能不满&#xff0c;该层所有的节点尽可能向左边靠拢。例如&#xff0c;图7.3中的4棵二叉树均为完全二叉树。实现数据结构CBTInserter有如下3种…...

Python算法例3 检测2的幂次

1. 问题描述 检测一个整数n是否为2的幂次。 2. 问题示例 n8&#xff0c;返回True&#xff1b;n6&#xff0c;返回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”固件&#xff0c;Base模式首先要将固件更新为“2 X Base Camera Link”。 右键SCI图标&#xff0c;选择“打开文件所在的位置”&#xff0c;找到并打开SciDalsaConfig的Demo&#xff0c;如上图所示&#xff1a; 左键单击“获取相机”&a…...

Gitee 发行版

Gitee 发行版 1、Gitee 发行版管理2、项目仓库中创建发行版本3、项目中导入3.1 gradle配置3.2 dependencies执行正常&#xff0c;包没有下载 1、Gitee 发行版管理 Gitee 发行版&#xff08;Release&#xff09;管理 2、项目仓库中创建发行版本 按照Gitee官网操作就行 3、项目…...

python面向对象

用animal举例代码如下&#xff1a; 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、范围&#xff08;range&#xff09; 1、数组 数组是具有相同唯一类型的一组已编号且长度固定的数据项序列&#xff0c;这种类型可以是任意的原始类型例如整型、字符串或者自定义类型。 Go 语言数组声明需要指定元素类型及元素个数&#xff0c;与…...

Error: no matching distribution found for tensorflow-cpu==2.6.*

目录 install_tensorflow()安装过程中遇到的问题 查找解决方案过程中&#xff1a; 解决办法&#xff1a; install_tensorflow()安装过程中遇到的问题 在服务器上安装tensorflow时&#xff0c;遇到了一个报错信息&#xff1a; 在网上找到一个类似的错误&#xff08;TensorFlow…...

nginx 进程模型

文章目录 nginx运行模式与进程模式进程模式流程图默认初始化运行模式与进程模式(宏展开)cpu_affinity多CPU绑定合理性判定Nginx的daemon创建&#xff08;os/unix/ngx_daemon.c&#xff09;运行模式、进程模式启动 多进程模式下master处理流程设置进程信号、初始化信号掩码、屏蔽…...

TypeScript - 枚举类型 -字符型枚举

什么是枚举 枚举就是有固定的元素的一个对象。 对象的元素可以直接列举出来。 什么是字符型枚举 字符型枚举&#xff0c;就是元素的值是字符串。 就这么简单。 定义一个我看看 来&#xff0c;让我们实际看一下字符型的枚举。 // 定义字符型枚举 enum COLOR2{RED red,BLUE blu…...

分布式锁-Redis红锁解决方案

一 分布式锁的概念 1&#xff1a;概念 分布式锁&#xff08;多服务共享锁&#xff09; 在分布式的部署环境下&#xff0c;通过锁机制来让多客户端互斥的对共享资源进行访问控制分布式系统不同进程共同访问共享资源的一种锁的实现。如果不同的系统或同一个系统的不同主机之间共…...

【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 问题描述&#xff1a; 使用 npm run dev 或者 yarn run dev 时 报错&#xff1a;Error: error:0308010C:digital envelope routines::unsupported PS D:\Project\dlspeed_all\GS-IMS\ruoyi-ui> npm run de…...

RTMP在智能眼镜行业应用方案有哪些?

方案示例 视频直播&#xff1a;智能眼镜通常具有摄像头和显示屏&#xff0c;可以实时拍摄和显示视频。RTMP协议可以用于将智能眼镜拍摄的视频传输到服务器&#xff0c;以便其他用户可以实时观看。远程协作&#xff1a;智能眼镜可以用于远程协作&#xff0c;例如在医疗、建筑等…...

【每日一题】合并两个有序数组

链接奉上&#xff1a;合并两个有序数组 目录 直接合并后排序&#xff1a;思路&#xff1a;代码实现&#xff1a; 双指针思路&#xff1a;代码实现&#xff1a; 直接合并后排序&#xff1a; 思路&#xff1a; 将nums2直接合并到nums1后边&#xff0c;并进行排序 代码实现&…...

MySQL---表的增查改删(CRUD进阶)

文章目录 数据库约束表的设计一对一一对多多对多 新增查询聚合查询分组查询联合查询内连接外连接自连接子查询合并查询 数据库约束 数据库约束就是指&#xff1a;程序员定义一些规则对数据库中的数据进行限制。这样数据库会在新增和修改数据的时候按照这些限制&#xff0c;对数…...

《HelloGitHub》第 91 期

兴趣是最好的老师&#xff0c;HelloGitHub 让你对编程感兴趣&#xff01; 简介 HelloGitHub 分享 GitHub 上有趣、入门级的开源项目。 github.com/521xueweihan/HelloGitHub 这里有实战项目、入门教程、黑科技、开源书籍、大厂开源项目等&#xff0c;涵盖多种编程语言 Python、…...

jvm线上异常排查流程

1. Linux命令 jps 找出当前运行实例 2. jinfo -flags pid&#xff08;java运行id) 打印出当前设置的jvm内存参数情况 3.jstat -gcutil pid 1000 10 每秒打印一次当前jvm的gc运行情况&#xff0c;一共打印10次 4.将gc日志下载进行分析&#xff1a;到底是因为什么原因导致一直…...

python项目之酒店客房入侵检测系统的设计与实现

项目简介 酒店客房入侵检测系统的设计与实现实现了以下功能&#xff1a; 1、控制台&#xff1a; 控制台是整个系统的首页面。在控制台中&#xff0c;酒店的客房管理人员能够在该页面中查看到当前的空余客房数量、当前在店的客房人数、当前的已用客房数量、当前酒店全部的客房…...

C++ 学习系列 -- 标准库常用得 algorithm function

一 前言 c 标准库中提供了许多操作数据结构&#xff1a;vector、list、deque、map、set 等函数&#xff0c;学习并了解这些常用函数对于我们理解 c 的一些设计模式有着重要的作用。 二 常用的 algorithm function 源码 源代码位置&#xff1a; bits/stl_algo.h 1. accumu…...

[论文笔记]E5

引言 今天又带来一篇文本匹配/文本嵌入的笔记:Text Embeddings by Weakly-Supervised Contrastive Pre-training。中文题目是 基于弱监督对比预训练计算文本嵌入。 本篇工作提出了E5模型(EmbEddings from bidirEctional Encoder rEpresentations)。该模型以带弱监督信号的对…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信

文章目录 Linux C语言网络编程详细入门教程&#xff1a;如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket&#xff08;服务端和客户端都要&#xff09;2. 绑定本地地址和端口&#x…...

《信号与系统》第 6 章 信号与系统的时域和频域特性

目录 6.0 引言 6.1 傅里叶变换的模和相位表示 6.2 线性时不变系统频率响应的模和相位表示 6.2.1 线性与非线性相位 6.2.2 群时延 6.2.3 对数模和相位图 6.3 理想频率选择性滤波器的时域特性 6.4 非理想滤波器的时域和频域特性讨论 6.5 一阶与二阶连续时间系统 6.5.1 …...

RocketMQ 客户端负载均衡机制详解及最佳实践

延伸阅读&#xff1a;&#x1f50d;「RocketMQ 中文社区」 持续更新源码解析/最佳实践&#xff0c;提供 RocketMQ 专家 AI 答疑服务 前言 本文介绍 RocketMQ 负载均衡机制&#xff0c;主要涉及负载均衡发生的时机、客户端负载均衡对消费的影响&#xff08;消息堆积/消费毛刺等…...

Java严格模式withResolverStyle解析日期错误及解决方案

在Java中使用DateTimeFormatter并启用严格模式&#xff08;ResolverStyle.STRICT&#xff09;时&#xff0c;解析日期字符串"2025-06-01"报错的根本原因是&#xff1a;模式字符串中的年份格式yyyy被解释为YearOfEra&#xff08;纪元年份&#xff09;&#xff0c;而非…...