当前位置: 首页 > 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…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 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全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

Java数值运算常见陷阱与规避方法

整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...

Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐&#xff1a;「storms…...

tauri项目,如何在rust端读取电脑环境变量

如果想在前端通过调用来获取环境变量的值&#xff0c;可以通过标准的依赖&#xff1a; std::env::var(name).ok() 想在前端通过调用来获取&#xff0c;可以写一个command函数&#xff1a; #[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 步…...