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

代码随想录算法训练营第14天 part01 | 二叉树理论基础篇

代码随想录

二叉树理论基础篇

二叉树的种类

二叉树有两种主要的形式:满二叉树和完全二叉树

满二叉树:如果一棵二叉树只有度为0的结点和度为2的结点,并且度为0的结点在同一层上,则这棵二叉树为满二叉树。
在这里插入图片描述
这棵二叉树为满二叉树,也可以说深度为k,有2^k-1个节点的二叉树。

完全二叉树

在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层(h从1开始),则该层包含 1~ 2^(h-1) 个节点。
在这里插入图片描述
优先级队列其实是一个堆,堆就是一棵完全二叉树,同时保证父子节点的顺序关系。

二叉搜索树

二叉搜索树是有数值的了,二叉搜索树是一个有序树。

若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
它的左、右子树也分别为二叉排序树

平衡二叉搜索树

平衡二叉搜索树:又被称为AVL(Adelson-Velsky and Landis)树,且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。
在这里插入图片描述
C++中map、set、multimap,multiset的底层实现都是平衡二叉搜索树,所以map、set的增删操作时间时间复杂度是logn,注意我这里没有说unordered_map、unordered_set,unordered_map、unordered_set底层实现是哈希表。

二叉树的存储

二叉树可以链式存储,也可以顺序存储。

那么链式存储方式就用指针顺序存储的方式就是用数组
在这里插入图片描述
顺序存储的方式如图:
在这里插入图片描述
用数组来存储二叉树如何遍历的呢?

如果父节点的数组下标是 i,那么它的左孩子就是 i * 2 + 1,右孩子就是 i * 2 + 2。

二叉树的遍历

二叉树主要有两种遍历方式:

  • 深度优先遍历:先往深走,遇到叶子节点再往回走。
  • 广度优先遍历:一层一层的去遍历。

深度优先遍历

	1、前序遍历(递归法,迭代法)2、中序遍历(递归法,迭代法)3、后序遍历(递归法,迭代法)

广度优先遍历

层次遍历(迭代法)

这里前中后,其实指的就是中间节点的遍历顺序

前序遍历:中左右
中序遍历:左中右
后序遍历:左右中

在这里插入图片描述
最后再说一说二叉树中深度优先和广度优先遍历实现方式,我们做二叉树相关题目,经常会使用递归的方式来实现深度优先遍历,也就是实现前中后序遍历,使用递归是比较方便的。

之前我们讲栈与队列的时候,就说过栈其实就是递归的一种实现结构,也就说前中后序遍历的逻辑其实都是可以借助栈使用递归的方式来实现的。

而广度优先遍历的实现一般使用队列来实现,这也是队列先进先出的特点所决定的,因为需要先进先出的结构,才能一层一层的来遍历二叉树。

在现场面试的时候 面试官可能要求手写代码,所以数据结构的定义以及简单逻辑的代码一定要锻炼白纸写出来。

public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) { this.val = val; }TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}
}

相关文章:

代码随想录算法训练营第14天 part01 | 二叉树理论基础篇

代码随想录 二叉树理论基础篇 二叉树的种类 二叉树有两种主要的形式:满二叉树和完全二叉树 满二叉树:如果一棵二叉树只有度为0的结点和度为2的结点,并且度为0的结点在同一层上,则这棵二叉树为满二叉树。 这棵二叉树为满二叉树…...

async与defer的区别

原文解释 async vs defer attributes - Growing with the Web...

奇数乘积(C语言)

一、运行结果&#xff1b; 二、源代码&#xff1b; # define _CRT_SECURE_NO_WARNINGS # include <stdio.h>int main() {//初始化变量值&#xff1b;int i 1;int j 3;//循环运算&#xff1b;while (j < 12){//运算&#xff1b;i i * j;//改变数值&#xff1b;j 2…...

中文分词库:jieba的词性对照表

jieba词性对照表 字母词性a形容词ad副形词ag形容词性语素an名形词b区别词c连词d副词dg副词素e叹词f方位词g语素h前接成分i成语j简称略称k后接成分l习用语m数词mq数量词n名词ng名词性语素nr人名ns地名nt机构团体名nz其他专名o拟声词p介词q量词r代词rg代词性语素rr人称代词rz指示…...

Linux:git的基础操作

git的下载 版本控制系统一般分为两种&#xff0c;集中式版本控制系统&#xff0c;分布式版本控制系统 什么是集中式版本控制系统&#xff1a;版本库集中存放在中央服务器&#xff0c;工作时候使用自己的电脑&#xff0c;当工作时候在中央服务器上拉取最新版本的代码&#xff0c…...

【华为OD机试】CPU 算力分配【C卷|100分】

【华为OD机试】-真题 !!点这里!! 【华为OD机试】真题考点分类 !!点这里 !! 题目描述 现有两组服务器A和B,每组有多个算力不同的CPU,其中 A[i] 是 A 组第 i 个CPU的运算能力, B[i] 是 B组 第 i 个CPU的运算能力。 一组服务器的总算力是各CPU的算力之和。 为了让两组服务器…...

挑战杯 机器视觉目标检测 - opencv 深度学习

文章目录 0 前言2 目标检测概念3 目标分类、定位、检测示例4 传统目标检测5 两类目标检测算法5.1 相关研究5.1.1 选择性搜索5.1.2 OverFeat 5.2 基于区域提名的方法5.2.1 R-CNN5.2.2 SPP-net5.2.3 Fast R-CNN 5.3 端到端的方法YOLOSSD 6 人体检测结果7 最后 0 前言 &#x1f5…...

基于Spring Boot的社区便民服务管理系统的设计与实现

摘 要 二十一世纪我们的社会进入了信息时代&#xff0c;信息管理系统的建立&#xff0c;大大提高了人们信息化水平。传统的管理方式对时间、地点的限制太多&#xff0c;而在线管理系统刚好能满足这些需求&#xff0c;在线管理系统突破了传统管理方式的局限性。于是本文针对这一…...

亚信安慧AntDB:数字化创新背后的数据力量

亚信安慧AntDB的“融合实时”的特性&#xff0c;不仅使得数据库具备了更强大的适应性&#xff0c;更让企业在不同业务场景下能够更好地实现业务目标&#xff0c;释放出更大的商业价值。融合实时的特性让AntDB具有了高度灵活性和实时性&#xff0c;使其能够满足企业在不同业务需…...

Matplotlib数据可视化实战-1数据可视化Matplotlib基础

1.1绘图的一般过程&#xff1a; 1.导入相关库 2.生成、读入或计算得到数据&#xff1b; 3.根据需要绘制折线图、散点图、柱状图、饼状图、雷达图、箱线图、三维曲线/曲面以及极坐标系图形&#xff1b; 4.根据需要设置图形属性&#xff1b; 5.显示或保存绘图结果。 例如&…...

信也科技发布消费者权益保护2023年度报告: 科技驱动、服务为先、合作共建社会化消保体系

3月15日消费者权益日当天&#xff0c;信也科技发布《消费者权益保护2023年度报告》&#xff08;下称《报告》&#xff0c;消费者权益保护简称“消保”&#xff09;。该报告为信也科技消保委员会成立后首份公开披露的消保工作年度总结。《报告》显示&#xff0c;信也科技通过智能…...

REDHAWK——连接(续)

文章目录 前言一、突发 IO1、数据传输①、输入②、输出 2、突发信号相关信息 (SRI)3、多输出端口4、使用复数数据①、在 C 中转换复数数据 5、时间戳6、端口统计①、C 二、消息传递1、消息生产者①、创建一个消息生产者②、发送消息 2、消息消费者①、创建消息消费者②、注册接…...

9.Python从入门到精通—Python 字符串格式化,三引号,Unicode 字符串

9.Python从入门到精通—Python 字符串格式化,三引号,Unicode 字符串 Python 字符串格式化Python 三引号Unicode 字符串创建 Unicode 字符串Python 的字符串内建函数 Python 字符串格式化 Python中的字符串格式化是指将一个字符串中的占位符替换为指定的值。Python中有多种字符串…...

O2OA(翱途)开发平台系统安全-用户登录IP限制

O2OA(翱途)开发平台[下称O2OA开发平台或者O2OA]支持对指定的用户设置可以连接的客户端计算机的IP地址&#xff0c;以避免用户在不安全的环境下访问系统。本篇主要介绍如何开启O2OA用户登录IP限制。 一、先决条件&#xff1a; 1、O2Server服务器正常运行&#xff0c;系统安装部…...

DirectShowPlayerService::doSetUrlSource: Unresolved error code 0x800c000d

报出这个问题&#xff0c;应该是对给的url解析不正确&#xff0c;我给的是rtsp的视频流地址&#xff0c;应该是对该格式解析异常。 所以参考两篇文&#xff1a; QT无法播放视频&#xff1a;报错&#xff1a;DirectShowPlayerService::doRender: Unresolved error code 0x8004…...

【测试流程及规范】8000字超详细完整版

前言&#xff1a; 首先注明该文由本人原创&#xff0c;转载时需注明出处&#xff1b;团队背景&#xff1a;测试团队加上我一共5名&#xff0c;Java开发10多位&#xff0c;前端3位&#xff0c;产品4位&#xff0c;还有架构工程师、运维等&#xff1b;公司IT团队开发的系统仅供内…...

第十四届蓝桥杯省赛真题 Java C 组【原卷】

文章目录 发现宝藏【考生须知】试题 A \mathrm{A} A : 求和试题 B: 分糖果试题 C: 三国游戏试题 D : \mathrm{D}: D: 平均试题 E \mathrm{E} E : 填充试题 F : \mathrm{F}: F: 棋盘试题 G: 子矩阵试题 H: 公因数匹配试题 I: 异或和之差试题 J : \mathrm{J}: J: 太阳 发现宝…...

v-model 粗略解析

v-model 粗略解析 v-model是什么&#xff1f; 双向数据绑定&#xff0c;可以从data流向页面&#xff0c;也可以从页面流向data通常用于表单收集&#xff0c;v-model 默认绑定 value 值书写形式&#xff1a; v-model:value"" 或 v-model v-model原理是什么&#xf…...

【vue elementUI】修改el-dropdown样式

实现效果如下&#xff1a; 代码如下&#xff1a; <el-dropdown trigger"click" command"handleCommand" active-text-color"#606266"><span class"product-card">{{getCategoryName(categoryId)}}</span><el-dro…...

6语言交易所/多语言交易所php源码/微盘PHP源码

6语言交易所PHP源码&#xff0c;简单测试了一下&#xff0c;功能基本都是正常的。 由于是在本地测试的运行环境的问题&#xff0c;K线接口有点问题&#xff0c;应该在正式环境下是OK的。 源码下载地址&#xff1a;6语言交易所/多语言交易所php源码/微盘PHP源码.zip 程序截图…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代&#xff0c;加密货币作为一种新兴的金融现象&#xff0c;正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而&#xff0c;加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下&#xff0c;稳定…...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

视觉slam十四讲实践部分记录——ch2、ch3

ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...