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࿰…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...

C++初阶-list的底层
目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...
uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖
在前面的练习中,每个页面需要使用ref,onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入,需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...
蓝桥杯 2024 15届国赛 A组 儿童节快乐
P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡,轻快的音乐在耳边持续回荡,小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下,六一来了。 今天是六一儿童节,小蓝老师为了让大家在节…...
测试markdown--肇兴
day1: 1、去程:7:04 --11:32高铁 高铁右转上售票大厅2楼,穿过候车厅下一楼,上大巴车 ¥10/人 **2、到达:**12点多到达寨子,买门票,美团/抖音:¥78人 3、中饭&a…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互
引擎版本: 3.8.1 语言: JavaScript/TypeScript、C、Java 环境:Window 参考:Java原生反射机制 您好,我是鹤九日! 回顾 在上篇文章中:CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...
Java数值运算常见陷阱与规避方法
整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...

Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统
💝💝💝欢迎莅临我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:「storms…...

tauri项目,如何在rust端读取电脑环境变量
如果想在前端通过调用来获取环境变量的值,可以通过标准的依赖: std::env::var(name).ok() 想在前端通过调用来获取,可以写一个command函数: #[tauri::command] pub fn get_env_var(name: String) -> Result<String, Stri…...
SQL Server 触发器调用存储过程实现发送 HTTP 请求
文章目录 需求分析解决第 1 步:前置条件,启用 OLE 自动化方式 1:使用 SQL 实现启用 OLE 自动化方式 2:Sql Server 2005启动OLE自动化方式 3:Sql Server 2008启动OLE自动化第 2 步:创建存储过程第 3 步:创建触发器扩展 - 如何调试?第 1 步:登录 SQL Server 2008第 2 步…...