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

leetcode-二叉树

  1. 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树&#xff0c;也即balance树&#xff0c;是一棵多路自平衡的搜索树。它类似普通的平衡二叉树&#xff0c;不同的一点是B树允许每个节点有更多的子节点。 B树内节点不存储数据&#xff0c;所有关键字都存储在叶子节点上。B树&#xff1a; B树&#xff1a; 二叉…...

【鸿蒙软件开发】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&#xff08;ypred​ 是输入&#xff0c;ytrue​ 是目标&#xff09;&#xff0c;定义逐点KL散度为&#xff1a; 为了在计算时避免下溢问题&#xff0c;此KLDivLoss期望输入在对数空间中。如果log_targetTrue&#xff0c;则目标…...

父子项目打包发布至私仓库

父子项目打包发布至私仓库 1、方法一 在不需要发布至私仓的模块上添加如下代码&#xff1a; <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编程案例点击跳转>软考全系列 &#x1f449;关于作者 专注于Android/Unity和各种游戏开发技巧&#xff0c;以及各种资源分享&…...

机器学习 | 决策树算法

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

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展开时样式 给容器一个高度&#xff0c;然后样式加上overflow: scroll&#xff0c;这样纵向滚动条就出来了。 <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 以上环境&#xff0c;如有新的版本&#xff0c;可自行选择安装新的版本为主 二.创建Wpf项目 1.项目的名称:MyToDo 项目名称:这里只是记录学习&#xff0c;所以随便命名都无所谓,只要觉得合理就…...

6G关键新兴技术- 智能超表面(RIS)技术演进

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

【redhat9.2】搭建Discuz-X3.5网站

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

算法篇 : 并查集

介绍 英文名&#xff1a;union find set 作用&#xff1a;合并集合&#xff0c;查询集合 合并&#xff1a;将有直接关系的顶点放在一个集合里面 查找&#xff1a;查询某个顶点所属的集合 集合的标志&#xff1a;用祖先点的标号作为每个集合的标识 案例 如果说将下图的集合2合并…...

AM@微积分基本定理@微积分第二基本定理

文章目录 abstract微积分第二基本定理微积分基本公式公式书写例 结合不定积分的方法求定积分定积分换元法证明 定积分换元公式逆用例 和不定积分第二类换元法的差别定积分分部积分法例 abstract 微积分第一基本定理告诉我们,总是能够通过积分法构造(表达)一个连续函数的原函数…...

goland常用快捷键

移动光标 控制光标的移动&#xff1a;fn上下左右 移至当前页的页头&#xff1a;ctrlPgUp 移至并选中光标到当前页头&#xff1a;ctrlshiftPgUp 移至当前页的页尾&#xff1a;ctrlPgDn 移至并选中当前光标到当前页尾&#xff1a;ctrlshiftPgDn 返回到当前的光标处&#xf…...

CSDN写文章时常见问题及技巧

CSDN写文章时常见问题及技巧 1.有序待续、更新中 1.有序 过程&#xff1a; 写 1.空格 &#xff0c;注意“.”后加个空格就可以生成序号&#xff0c;随心所欲编辑了 待续、更新中 ————————————————————— 以上就是今日博客的全部内容了 创作不易,若对您有…...

JVM虚拟机详解

目录 01JVM由哪些部分组成/运行流程 什么是程序计数器 详细介绍堆 介绍方法区&#xff08;Method Area&#xff09; 直接内存 虚拟机栈(Java Virtual machine Stacks) 垃圾回收是否涉及栈内存 栈内存分配越大越好吗 方法内的局部变量是否线程安全 什么情况下会导致栈…...

Go 怎么操作 OSS 阿里云对象存储

1 介绍 在项目开发中&#xff0c;我们经常会使用对象存储&#xff0c;比如 Amazon 的 S3&#xff0c;腾讯云的 COS&#xff0c;阿里云的 OSS 等。本文我们以阿里云 OSS 为例&#xff0c;介绍怎么使用 Go 操作对象存储。 阿里云 OSS 提供了 REST Api 和 OSS Go SDK&#xff0…...

ElasticSearch搜索引擎之倒排索引及其底层算法

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

嵌入式学习笔记DAY33(网络编程——TCP)

一、网络架构 C/S &#xff08;client/server 客户端/服务器&#xff09;&#xff1a;由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序&#xff0c;负责提供用户界面和交互逻辑 &#xff0c;接收用户输入&#xff0c;向服务器发送请求&#xff0c;并展示服务…...

Git常用命令完全指南:从入门到精通

Git常用命令完全指南&#xff1a;从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...

【FTP】ftp文件传输会丢包吗?批量几百个文件传输,有一些文件没有传输完整,如何解决?

FTP&#xff08;File Transfer Protocol&#xff09;本身是一个基于 TCP 的协议&#xff0c;理论上不会丢包。但 FTP 文件传输过程中仍可能出现文件不完整、丢失或损坏的情况&#xff0c;主要原因包括&#xff1a; ✅ 一、FTP传输可能“丢包”或文件不完整的原因 原因描述网络…...

qt+vs Generated File下的moc_和ui_文件丢失导致 error LNK2001

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

01-VMware16虚拟机详细安装

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

IDEA中微服务指定端口启动

在使用IDEA开发SpringBoot微服务时&#xff0c;经常需要开启多个服务实例以测试负载均衡&#xff0c;以下几种方法开启不同端口。 直接在配置文件中指定 # application.propertiesserver.port8001指定VM参数 点击Modify options&#xff0c;选择Add VM options&#xff0c;值…...

Vue项目PDF目录功能集成【一】——方案深度思考

文章目录 项目背景一、方案一&#xff1a;数据透传 外部开发模式二、方案二&#xff1a;内置组件 黑盒模式三、方案三&#xff1a;激活官方实现 可控定制总结 项目背景 本项目是Vue 3 项目&#xff0c;需要使用文件预览组件&#xff08;pdfjs 当前是作为sdk二次封装引入&am…...

因泰立科技H1X激光雷达:因泰立科技为智慧工业注入新动力

在当今工业领域&#xff0c;精准测量与高效作业是推动产业升级的关键因素。因泰立科技推出的H1X三维轮廓扫描激光雷达&#xff0c;凭借其卓越的性能和广泛的应用场景&#xff0c;正成为智慧工业中不可或缺的高科技装备。 产品简介 H1X三维轮廓扫描激光雷达是因泰立科技基于二维…...

MongoDB慢查询临时开启方法讲解

1、首先连接数据库 mongosh "mongodb://localhost:27017" 2、选择目标数据库 show databases;#显示所有数据库 use lidb;#使用某数据库 3、查看当前分析级别 db.getProfilingStatus() 输出 { was: 0, slowms: 100, sampleRate: 1, ok: 1 } #was0表示关闭&…...