当前位置: 首页 > 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)。该模型以带弱监督信号的对…...

51c自动驾驶~合集58

我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留&#xff0c;CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制&#xff08;CCA-Attention&#xff09;&#xff0c;…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

Spring AI与Spring Modulith核心技术解析

Spring AI核心架构解析 Spring AI&#xff08;https://spring.io/projects/spring-ai&#xff09;作为Spring生态中的AI集成框架&#xff0c;其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似&#xff0c;但特别为多语…...

鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南

1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发&#xff0c;使用DevEco Studio作为开发工具&#xff0c;采用Java语言实现&#xff0c;包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...

微服务通信安全:深入解析mTLS的原理与实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、引言&#xff1a;微服务时代的通信安全挑战 随着云原生和微服务架构的普及&#xff0c;服务间的通信安全成为系统设计的核心议题。传统的单体架构中&…...

数据库——redis

一、Redis 介绍 1. 概述 Redis&#xff08;Remote Dictionary Server&#xff09;是一个开源的、高性能的内存键值数据库系统&#xff0c;具有以下核心特点&#xff1a; 内存存储架构&#xff1a;数据主要存储在内存中&#xff0c;提供微秒级的读写响应 多数据结构支持&…...

【51单片机】4. 模块化编程与LCD1602Debug

1. 什么是模块化编程 传统编程会将所有函数放在main.c中&#xff0c;如果使用的模块多&#xff0c;一个文件内会有很多代码&#xff0c;不利于组织和管理 模块化编程则是将各个模块的代码放在不同的.c文件里&#xff0c;在.h文件里提供外部可调用函数声明&#xff0c;其他.c文…...