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

10.30二叉树一些性质,找公共祖先(一般与搜索树),操作的复杂度,选择题细节

课上

 

一些结论,性质

n0,n1,n2指的是子结点的数量,n0没有子节点,叶子结点

n=2*n2+n1+1,若n1为奇数,则n为偶数,不然,则为奇数

满二叉树

没有度为1的结点,即每个结点要么没有孩子结点,要么就有两个孩子结点

没有孩子结点的结点一定是叶子结点

回顾 

寻找二叉搜索树最近公共祖先

思路是找到从根节点到两个结点的路径,由于是一个树,所以最开始的路径是一定一样的,即在同一颗树上至少具有相同的根节点,然后一直往下走,走到最后一个分岔口,开始分叉,即路径中最后一个相同的结点时,就是最近公共祖先

始终保持最近的相同结点,可以在退出时直接返回最后一个相同的结点,即最近公共祖先

找根节点到目标结点的路径,是从根节点开始

每次迭代中,先入当前结点,再更新,最后迭代结束,加入目标值

寻找二叉树的公共祖先

思路还是找路径,然后返回最后一个相同的结点

但由于不是搜索树,不满足左子树比根节点小,右子树比根节点大的性质,所以找路径的方法不同

采用dfs方式找路径,如果已经找到了,或者是叶子结点尝试继续向下,则直接返回

不然就是还没找到,先把当前的结点入列,然后判断是不是目标值,如果是就打上标记并直接返回

不然,继续递归向下

遍历两个孩子,看flag,如果在左子树里找到了,flag就会为1,那么在右子树中就不会继续递归,不然继续

最后都遍历完后,可能找到了,也可能没找到,找到了就直接返回,不操作,不然就说明当下的子树里没有,应该回溯

二叉树性质,复杂度

对于二叉树,我们维护一个堆,插入和依次获取元素的时间复杂度皆为O(logn)

插入

将元素插入最后一位,再进行向上冒泡,即如果父节点的值小于被插入的元素,父节点下移,被插入的元素上移。时间复杂度取决于树的高度h。而完全二叉树的树的高度为[logn+1]的上取整,所示时间复杂度为O(logn)。

n是插入前的树的结点数,插入完后n++

选择题

 

 

插入排序需要不断移动左序列,即遍历到的位置之前是有序的,后面是无序的,只有到最后才完全有序;选择排序是每次选一个最大的交换到序列的相应尾端位置;冒泡排序也是这个思路,只不过选择排序是选后交换,每次只用一次,但冒泡排序选和交换同时进行,每次至少需要一次

快速排序在有序时最慢为n^2,原因

标记,一些与……无关的排序

元素的移动次数与关键字的初始排列次序无关的是:基数排序

元素的比较次数与初始序列无关是:选择排序

算法的时间复杂度与初始序列无关的是:选择排序

最坏的情况和最好的情况恰好相反,在指定好比较的方向下

如果是从左到右,每次都和有序的第一个(当前的最小)比较,那么逆序是最好,顺序是最坏

这时插入的判断条件是找到左边为空或比左边大,右边为空或比右边小的位置

如果是从右到左,每次都和有序的最后一个(当前的最大)比较,那么逆序是最坏,顺序是最好

因为逆序时,每次接下来的牌都是当前的最小,顺序时,每次的牌都是当前的最大

相关文章:

10.30二叉树一些性质,找公共祖先(一般与搜索树),操作的复杂度,选择题细节

课上 一些结论,性质 n0,n1,n2指的是子结点的数量,n0没有子节点,叶子结点 n2*n2n11,若n1为奇数,则n为偶数,不然,则为奇数 满二叉树 没有度为1的结点,即每个结点要么没有孩子结点,要么…...

亮氨酸脯氨酸肽——一种新型的医药中间体研究肽

亮氨酸脯氨酸医药中间体肽是一种合成(人造)激素,类似于大脑中产生的天然激素。它用于治疗许多医疗问题,包括: 子宫平滑肌瘤(子宫肌瘤)出血引起的贫血,或晚期或晚期前列腺癌症&#…...

Ubuntu 22.04 开机闪logo后卡在/dev/sda3: clean

环境 Vmware 17.0.0,CPU 2,内存4G,硬盘50G Ubuntu 22.04 问题描述 开机 --> 显示两行代码 --> 显示ubuntu logo --> 左上显示两个代码卡住不动 原因分析 1、网上大多说显卡驱动,最近没安装相关软件,也没…...

avue-crud 自定义列

基本设置: option: {columnBtn: false,refreshBtn: false,addBtn: false,delBtn: false,editBtn: false,viewBtn: false,searchShowBtn: false,height: auto,maxHeight: auto,calcHeight: 70,searchLabelWidth: 58,tip: false,searchShow: false,searchMenuSpan: 6…...

达索系统SOLIDWORKS 2024 装配体新增功能

如今市场环境紧迫,许多企业在这样的情形之下,都需要尽快将产品推向市场,赢得头筹。所以产品设计需要快速进行装配验证,以确保产品功能和性能的准确性和可靠性,同时原型或样机的制造和装配需要尽快完成,以满…...

电脑入门:电脑专业英语500词,供新手参考

1. file n. 文件;v. 保存文件 2. command n. 命令,指令 3. use v. 使用,用途 4. program n. 程序 5. line n. (数据,程序)行,线路 6. if conj. 如果 7. display vt. 显示,显示器 8. set v. 设置,n. 集合 9. key n. 键,关键字,关键码 10. list n. 列表,显示,…...

采购管理工具-采购软件-Leangoo免费看板工具

我们可以按照公司的实际情况定制采购流程。 1、在Leangoo免费看板工具中创建一个项目,项目类型建议选择“轻量级协作”,项目模版建议选择“人事与行政” 系统会自动为您创建四个看板,如下图: 图1 2、在项目内创建一个 “办公室采…...

【23真题】大神凭这套拿452分!看看你能拿多少?

今天分享的是23年福州大学866的信号与系统试题及解析。23年福州大学新一代电子信息的最高分是452分!但是我看不到单科分数。按照75,75,150,150。也就是只有450,说明这个同学,专业课和数学几乎拿满&#xff…...

大数据之LibrA数据库系统告警处理(ALM-12002 HA资源异常)

告警解释 HA软件周期性检测Manager的WebService浮动IP地址和数据库。当HA软件检测到浮动IP地址或数据库异常时,产生该告警。 当HA检测到浮动IP地址或数据库正常后,告警恢复。 告警属性 告警参数 对系统的影响 如果Manager的WebService浮动IP地址异常…...

CSS基础入门04

目录 1.内边距 1.1基础写法 1.2复合写法 2.外边距 2.1基础写法 2.2复合写法 2.3块级元素水平居中 3.去除浏览器默认样式 4.弹性布局 4.1初体验 5.flex 布局基本概念 6.常用属性 6.1justify-content 6.2align-items 1.内边距 padding 设置内容和边框之间的距离. …...

LeetCode2741.特别的排列 状压

暴力枚举的话是n&#xff01; 考虑状压DP&#xff0c;其实就是用二进制表示状态 再进行暴力 同时加一个记忆化就好了 这里有常用技巧&#xff1a; 全集&#xff08;1<<n&#xff09;-1 增加某个元素 x | (1<<i) 删除某个元素 x & ~(1<<i) const i…...

【Linux】Centos 8 服务器部署:阿里云域名注册、域名解析、个人网站 ICP 备案详细教程

目录 一、背景信息 二、操作步骤 &#xff08;1&#xff09;查询域名 &#xff08;2&#xff09;加入域名清单 &#xff08;3&#xff09;确认订单信息 &#xff08;4&#xff09;支付 &#xff08;5&#xff09;等待域名实名认证通过 三、域名注册成功 四、查看域名…...

Sass、Less和Stylus之间有什么主要的区别?

Sass、Less和Stylus是三种常见的CSS预处理器&#xff0c;它们在功能和语法上有一些区别。以下是它们之间的主要区别&#xff1a; 1&#xff1a;语法差异&#xff1a; Sass使用缩进的语法&#xff0c;使用类似于Python的缩进来表示嵌套规则和块级作用域。Less和Stylus使用类似…...

第八章 软件测试自动化

一、学习目的与要求 通过本章的学习&#xff0c;了解自动化测试应考虑的各种因素及如何衡量自动化测试成本&#xff0c;掌握自动化测试和手工测试的优缺点&#xff0c;能正确选择软件测试策略&#xff0c;了解测试工 具的分类和使用目的&#xff0c;熟悉常用的测试工具&#xf…...

科大讯飞勾勒生成式AI输入法“模样”,开启下一代输入法革命

回顾国内第三方输入法赛道近十余年的发展&#xff0c;移动互联网的市场红利催生了科大讯飞、百度、搜狗等颇具规模和实力的头部厂商。与此同时&#xff0c;历经多年、多方角逐&#xff0c;第三方输入法市场进入存量阶段&#xff0c;升级技术、优化用户体验来挖掘存量&#xff0…...

OV-VG: A Benchmark for Open-Vocabulary Visual Grounding

OV-VG: A Benchmark for Open-Vocabulary Visual Grounding 一、Abstract 写在前面 又是一周周末&#xff0c;光调代码去了&#xff0c;都没时间看论文了&#xff0c;汗。   这是一篇关于开放词汇定位的文章&#xff0c;也是近两年的新坑&#xff0c;但是资源也是需要不少。 …...

win10 javaweb 项目8080端口被占用

文章目录 前言出现场景&#xff1a;解决思路&#xff1a; 前言 提示&#xff1a;生活该走向何处&#xff1f;也许你还不知道答案&#xff0c;但是你一定是答案的一部分。 出现场景&#xff1a; 解决思路&#xff1a; 找到运行的进程直接干掉 打开命令窗口&#xff08;win r…...

C语言每日一题(22)合并两个有序数组

力扣网 88. 合并两个有序数组 题目描述 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2&#xff0c;另有两个整数 m 和 n &#xff0c;分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中&#xff0c;使合并后的数组同样按 非递减顺序 排列。 注意…...

C++学习day--24 推箱子游戏图像化开发

环境要求&#xff1a; 1、VS2015以上 2、成功安装并配置图形库 项目注意事项&#xff1a;代码复制好以后&#xff0c;把下面的字符集改为多字节字符集 第 1 节 项目需求 实现一款推箱子游戏&#xff0c;效果如下图所示 , 具体规则&#xff1a; 1. 箱子只能推动而不能拉动…...

YOLOv8中的After Fuse指的是什么?

Fuse是指模型的一些模块进行融合。常见的就是conv和bn层进行融合,在训练的时候模型是存在conv和bn的,但在推理的过程中,模型在初始化的时候会进行模型fuse,把其中的conv和bn进行融合,通过一些数学转换把bn层融合到conv里面,还有一些例如DBB,RepVGG等等模块支持融合的这些在fuse…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

【git】把本地更改提交远程新分支feature_g

创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

C++:多态机制详解

目录 一. 多态的概念 1.静态多态&#xff08;编译时多态&#xff09; 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1&#xff09;.协变 2&#xff09;.析构函数的重写 5.override 和 final关键字 1&#…...

20个超级好用的 CSS 动画库

分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码&#xff0c;而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库&#xff0c;可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画&#xff0c;可以包含在你的网页或应用项目中。 3.An…...

JavaScript 数据类型详解

JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型&#xff08;Primitive&#xff09; 和 对象类型&#xff08;Object&#xff09; 两大类&#xff0c;共 8 种&#xff08;ES11&#xff09;&#xff1a; 一、原始类型&#xff08;7种&#xff09; 1. undefined 定…...

深入理解Optional:处理空指针异常

1. 使用Optional处理可能为空的集合 在Java开发中&#xff0c;集合判空是一个常见但容易出错的场景。传统方式虽然可行&#xff0c;但存在一些潜在问题&#xff1a; // 传统判空方式 if (!CollectionUtils.isEmpty(userInfoList)) {for (UserInfo userInfo : userInfoList) {…...