leetcode-二叉树
- B树和B+树的区别
- B树,也即balance树,是一棵多路自平衡的搜索树。它类似普通的平衡二叉树,不同的一点是B树允许每个节点有更多的子节点。
- B+树内节点不存储数据,所有关键字都存储在叶子节点上。
- B树:
B+树:
二叉树理论基础:
1.种类:满二叉树、完全二叉树、二叉搜索树、平衡二叉树。
完全二叉树是最后一行从左到右连续但不一定全满。
二叉搜索树,必须有一定顺序。查询和添加都是O(logn),因为添加就是查询的过程。
平衡二叉搜索树:左右子树高度差的绝对值不超过1。map,set,multimap,multiset底层都是平衡二叉搜索树(是红黑树,红黑树是一种平衡二叉搜索树。)
2.存储方式:链表、数组。
链表,就是val,Treenode* left, Treenode *right
数组,一开始从0开始,左孩子就是2k+1,右孩子就是2k+2
3.遍历方式:
深度优先搜索:前序(中左右)、中序(左中右)、后序(左右中)。一般用递归实现,也可以迭代实现。
广度优先搜索:层序遍历是其中一种。
图的深度优先搜索就对应树的前中后序,图的广度优先搜索就对应树的层序遍历。
1. 二叉树的前,中,后序遍历 - 递归 leetcode144.94.145 20231026
代码随想录又卡了,栈与队列最后那题打着C++已实现的优先队列的旗号实际上是堆,而堆本身又是完全二叉树.....优先队列那题还不是直接拿的priority_queue去实现的,还自定义了它的比较规则,这又引出一个函数对象的概念,总之是无从下手,遂转战二叉树。今天看了看二叉树的理论知识,感觉还行,结果写题的时候又被递归摆了一道,完全忘了return和题干给的函数有什么用。
总之,题干给的preorderTraversal没动,自己重新实现了一个函数,调用之即可。下面两题是类似的。
class Solution { public:void preorder(TreeNode* cur, vector<int>& vct) {if(cur == nullptr){return;}vct.push_back(cur->val);preorder(cur->left,vct);preorder(cur->right,vct);}vector<int> preorderTraversal(TreeNode* root){vector<int> vct;preorder(root,vct);return vct;}};
2. 二叉树的前,中,后序遍历 - 迭代leetcode144.94.145 20231027
迭代分为前后,中两种,理解起来其实还是很困难的,看代码貌似记住了,自己写对了,但是再过几天让我写是绝对写不出来的
前后之所以说是“一种”,因为后序可以由前序倒一下左右,再reverse一下数组就能得到。他们遍历和处理的顺序都是一样的,而中序就不一样了。
下面来看一下具体的代码~
前序,后序在这里就只放前序了:
class Solution { public:vector<int> preorderTraversal(TreeNode* root) {stack<TreeNode*> stk;vector<int> vct;if(root == nullptr)return vct;stk.push(root);while(!stk.empty()){TreeNode* cur = stk.top();stk.pop();vct.push_back(cur->val);if(cur->right !=nullptr)stk.push(cur->right);if(cur->left !=nullptr)stk.push(cur->left);}return vct;} };
定义一个stk用于模拟递归,一个vct用户返回数组。因为要先push root进去,所以先得判断一下是否为空。
root被push进去以后,只要栈不为空,就pop栈顶出来,再把刚出的栈顶push到 vct 里面去,然后先往栈里push右边,再往栈里push左边。这样的话,之后vct就会从栈顶开始出,就会先被push_back到vct里面去,而后又是往复的右左栈入,中(栈里元素)左右vct出。
中序
class Solution { public:vector<int> inorderTraversal(TreeNode* root) {vector<int> vct;stack<TreeNode*> stk;TreeNode* cur = root;while(cur != nullptr || !stk.empty()){if(cur != nullptr){stk.push(cur);cur = cur->left;//入栈,然后cur一直到最左边}else{cur = stk.top();//已经为空了,就取栈头的成为现在的curstk.pop();vct.push_back(cur->val);cur = cur->right;}}return vct;} };
未完待续
相关文章:

leetcode-二叉树
B树和B树的区别 B树,也即balance树,是一棵多路自平衡的搜索树。它类似普通的平衡二叉树,不同的一点是B树允许每个节点有更多的子节点。 B树内节点不存储数据,所有关键字都存储在叶子节点上。B树: B树: 二叉…...

【鸿蒙软件开发】ArkTS基础组件之TextTimer(文本显示计时)、TimePicker(时间选择)
文章目录 前言一、TextTimer1.1 子组件1.2 接口参数TextTimerController 1.3 属性1.4 事件1.5 示例代码 二、TimePicker2.1 子组件2.2 接口参数 2.3 属性2.4 事件TimePickerResult对象说明 2.5 示例代码 总结 前言 通过文本显示计时信息并控制其计时器状态的组件。 时间选择组…...

pytorch 笔记:KLDivLoss
1 介绍 对于具有相同形状的张量 ypred 和 ytrue(ypred 是输入,ytrue 是目标),定义逐点KL散度为: 为了在计算时避免下溢问题,此KLDivLoss期望输入在对数空间中。如果log_targetTrue,则目标…...

父子项目打包发布至私仓库
父子项目打包发布至私仓库 1、方法一 在不需要发布至私仓的模块上添加如下代码: <plugin><groupId>org.apache.maven.plugins</groupId><artifactId>maven-deploy-plugin</artifactId><configuration><skip>true</s…...
汽车网络安全--ECU的安全更新
目前,汽车ECU的软件更新可以总结分成三大类: 工厂刷写模式:工厂大批量刷写或者升级,一般在出厂用; 工程模式:4S店、工厂等专业人员进行的ECU固件更新,通常是动力、转向、车控等; 车主模式:车主根据云端推送信息,通过IVI进行应用软件更新;目前也有趋势通过这种方式刷…...
NLP之搭建RNN神经网络
文章目录 代码展示代码意图代码解读知识点介绍1. Embedding2. SimpleRNN3. Dense 代码展示 # 构建RNN神经网络 from tensorflow.keras.models import Sequential from tensorflow.keras.layers import Dense, SimpleRNN, Embedding import tensorflow as tfrnn Sequential() …...

Android问题笔记四十三:JNI 开发如何快速定位崩溃问题
点击跳转>Unity3D特效百例点击跳转>案例项目实战源码点击跳转>游戏脚本-辅助自动化点击跳转>Android控件全解手册点击跳转>Scratch编程案例点击跳转>软考全系列 👉关于作者 专注于Android/Unity和各种游戏开发技巧,以及各种资源分享&…...

机器学习 | 决策树算法
一、决策树算法概述 1、树模型 决策树:从根节点开始一步步走到叶子节点(决策)。所有的数据最终都会落到叶子节点,既可以做分类也可以做回归。 在分类问题中,表示基于特征对实例进行分类的过程,可以认为是if-then的集合࿰…...

javascript中各种风骚的代码
1.判断数值符号是否相同 function numericSymbolsIsEqual(x: number, y: number): boolean {return (x ^ y) > 0}console.log(numericSymbolsIsEqual(1, 1))console.log(numericSymbolsIsEqual(-1, 1))console.log(numericSymbolsIsEqual(1, -1))console.log(numericSymbols…...

el-tree横向纵向滚动条
el-tree未展开时样式 el-tree展开时样式 给容器一个高度,然后样式加上overflow: scroll,这样纵向滚动条就出来了。 <el-card style"height: 528px;overflow: scroll"><el-inputplaceholder"输入关键字进行过滤"v-model&…...

STM32G030F6P6 芯片实验 (一)
STM32G030F6P6 芯片实验 (一) 淘宝搞了几片, 没试过 G系列, 试试感觉. 先搞片小系统版: 套 STM32F103C8T6小系统板格式. 原理图: (1) Ref 有点跳, 从 STM32F103C8T6 系统板改的, 没重编号. (2) Type-C 纯给电, 砍了 16pin的, 直接换 6pin的。 (3) 测试LED放 B2。 (4) 测试底…...

Wpf 使用 Prism 实战开发Day01
一.开发环境准备 1. VisualStudio 2022 2. .NET SDK 7.0 3. Prism 版本 8.1.97 以上环境,如有新的版本,可自行选择安装新的版本为主 二.创建Wpf项目 1.项目的名称:MyToDo 项目名称:这里只是记录学习,所以随便命名都无所谓,只要觉得合理就…...

6G关键新兴技术- 智能超表面(RIS)技术演进
摘要: 根据欧盟5G公私联盟协会定义,可重构智慧表面技术是由能够任意塑造电磁波面的材料组成,几乎是被动设备,可以适应或改变发射器和接收器之间的无线电信号。 一、产品定义及范围 根据欧盟5G公私联盟协会(5G Infrastructure P…...

【redhat9.2】搭建Discuz-X3.5网站
步骤 1.配置软件仓库 2.安装对应的软件 httpd php* mariadb* 3.启动服务 httpd mariadb 4.配置数据库 创建数据库 修改root密码 数据库的 5.传源码包(Discuz-X3.5) 解压 6.web页面初始化 关闭防火墙 允许http服务通过 修改权限 实…...

算法篇 : 并查集
介绍 英文名:union find set 作用:合并集合,查询集合 合并:将有直接关系的顶点放在一个集合里面 查找:查询某个顶点所属的集合 集合的标志:用祖先点的标号作为每个集合的标识 案例 如果说将下图的集合2合并…...
AM@微积分基本定理@微积分第二基本定理
文章目录 abstract微积分第二基本定理微积分基本公式公式书写例 结合不定积分的方法求定积分定积分换元法证明 定积分换元公式逆用例 和不定积分第二类换元法的差别定积分分部积分法例 abstract 微积分第一基本定理告诉我们,总是能够通过积分法构造(表达)一个连续函数的原函数…...
goland常用快捷键
移动光标 控制光标的移动:fn上下左右 移至当前页的页头:ctrlPgUp 移至并选中光标到当前页头:ctrlshiftPgUp 移至当前页的页尾:ctrlPgDn 移至并选中当前光标到当前页尾:ctrlshiftPgDn 返回到当前的光标处…...
CSDN写文章时常见问题及技巧
CSDN写文章时常见问题及技巧 1.有序待续、更新中 1.有序 过程: 写 1.空格 ,注意“.”后加个空格就可以生成序号,随心所欲编辑了 待续、更新中 ————————————————————— 以上就是今日博客的全部内容了 创作不易,若对您有…...

JVM虚拟机详解
目录 01JVM由哪些部分组成/运行流程 什么是程序计数器 详细介绍堆 介绍方法区(Method Area) 直接内存 虚拟机栈(Java Virtual machine Stacks) 垃圾回收是否涉及栈内存 栈内存分配越大越好吗 方法内的局部变量是否线程安全 什么情况下会导致栈…...
Go 怎么操作 OSS 阿里云对象存储
1 介绍 在项目开发中,我们经常会使用对象存储,比如 Amazon 的 S3,腾讯云的 COS,阿里云的 OSS 等。本文我们以阿里云 OSS 为例,介绍怎么使用 Go 操作对象存储。 阿里云 OSS 提供了 REST Api 和 OSS Go SDK࿰…...

ElasticSearch搜索引擎之倒排索引及其底层算法
文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

嵌入式学习笔记DAY33(网络编程——TCP)
一、网络架构 C/S (client/server 客户端/服务器):由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序,负责提供用户界面和交互逻辑 ,接收用户输入,向服务器发送请求,并展示服务…...
Git常用命令完全指南:从入门到精通
Git常用命令完全指南:从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...
【FTP】ftp文件传输会丢包吗?批量几百个文件传输,有一些文件没有传输完整,如何解决?
FTP(File Transfer Protocol)本身是一个基于 TCP 的协议,理论上不会丢包。但 FTP 文件传输过程中仍可能出现文件不完整、丢失或损坏的情况,主要原因包括: ✅ 一、FTP传输可能“丢包”或文件不完整的原因 原因描述网络…...

qt+vs Generated File下的moc_和ui_文件丢失导致 error LNK2001
qt 5.9.7 vs2013 qt add-in 2.3.2 起因是添加一个新的控件类,直接把源文件拖进VS的项目里,然后VS卡住十秒,然后编译就报一堆 error LNK2001 一看项目的Generated Files下的moc_和ui_文件丢失了一部分,导致编译的时候找不到了。因…...

01-VMware16虚拟机详细安装
官网地址:https://www.vmware.com/cn.html 1.1 打开下载好的 .exe 文件, 双击安装。 1.2 点击下一步 1.3 先勾选我接受许可协议中的条款,然后点击下一步 1.4 自定义安装路径,注意这里的文件路径尽量不要包含中文,完成…...

IDEA中微服务指定端口启动
在使用IDEA开发SpringBoot微服务时,经常需要开启多个服务实例以测试负载均衡,以下几种方法开启不同端口。 直接在配置文件中指定 # application.propertiesserver.port8001指定VM参数 点击Modify options,选择Add VM options,值…...
Vue项目PDF目录功能集成【一】——方案深度思考
文章目录 项目背景一、方案一:数据透传 外部开发模式二、方案二:内置组件 黑盒模式三、方案三:激活官方实现 可控定制总结 项目背景 本项目是Vue 3 项目,需要使用文件预览组件(pdfjs 当前是作为sdk二次封装引入&am…...

因泰立科技H1X激光雷达:因泰立科技为智慧工业注入新动力
在当今工业领域,精准测量与高效作业是推动产业升级的关键因素。因泰立科技推出的H1X三维轮廓扫描激光雷达,凭借其卓越的性能和广泛的应用场景,正成为智慧工业中不可或缺的高科技装备。 产品简介 H1X三维轮廓扫描激光雷达是因泰立科技基于二维…...
MongoDB慢查询临时开启方法讲解
1、首先连接数据库 mongosh "mongodb://localhost:27017" 2、选择目标数据库 show databases;#显示所有数据库 use lidb;#使用某数据库 3、查看当前分析级别 db.getProfilingStatus() 输出 { was: 0, slowms: 100, sampleRate: 1, ok: 1 } #was0表示关闭&…...