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

随想录二刷Day15——二叉树

文章目录

  • 二叉树
    • 2. 递归遍历二叉树
    • 3. 二叉树的迭代遍历
    • 4. 二叉树的统一迭代法

二叉树

2. 递归遍历二叉树

144. 二叉树的前序遍历

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> result;preorder(root, result);return result;}private:void preorder(TreeNode *root, vector<int> &result) {if (root == NULL) return ;result.push_back(root->val);preorder(root->left, result);preorder(root->right, result);} 
};

94. 二叉树的中序遍历

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> result;inorder(root, result);return result;}private:void inorder(TreeNode *root, vector<int> &result) {if (root == NULL) return ;inorder(root->left, result);result.push_back(root->val);inorder(root->right, result);}
};

145. 二叉树的后序遍历

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> result;postorder(root, result);return result;}private:void postorder(TreeNode *root, vector<int> &result) {if (root == NULL) return ;postorder(root->left, result);postorder(root->right, result);result.push_back(root->val);}
};

3. 二叉树的迭代遍历

144. 二叉树的前序遍历

遍历顺序:中左右
压栈顺序:中(直接弹出)右左

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> result;if (root == NULL) return result;stack<TreeNode *> stk;stk.push(root);while ( !stk.empty() ) {TreeNode *cur = stk.top();stk.pop();result.push_back(cur->val); // 中if (cur->right) stk.push(cur->right); // 右if (cur->left) stk.push(cur->left); // 左}return result;}
};

145. 二叉树的后序遍历

先序遍历:中左右
后序遍历:左右中
所以把先序遍历的压栈顺序修改,得到遍历 中右左 的顺序,然后翻转遍历结果。

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> result;if (root == NULL) return result;stack<TreeNode *> stk;stk.push(root);while ( !stk.empty() ) {TreeNode *cur = stk.top();stk.pop();result.push_back(cur->val); // 中if (cur->left) stk.push(cur->left); // 左if (cur->right) stk.push(cur->right); // 右}reverse(result.begin(), result.end()); // 此时遍历顺序为 中右左,翻转得到后序遍历的结果return result;}
};

94. 二叉树的中序遍历

中序遍历不太一样,要借助指针查看左子节点是否为空,来得到左中右的遍历结果

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode *> stk;TreeNode *cur = root;while ( cur != NULL || !stk.empty() ) {if (cur != NULL) { // 如果当前节点不空,则一直找左子节点stk.push(cur);cur = cur->left;} else {cur = stk.top(); // 上个节点的左节点已经找完了stk.pop();result.push_back(cur->val); // 左完了该中cur = cur->right; // 中完了去看右子树}}return result;}
};

4. 二叉树的统一迭代法

统一遍历方式,按遍历顺序的逆序输出结果。

144. 二叉树的前序遍历

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode *> stk;if (root) stk.push(root);while ( !stk.empty() ) {TreeNode *cur = stk.top();stk.pop();if (cur) { // 遇到 null 说明是待处理节点if (cur->right) stk.push(cur->right); // 右if (cur->left) stk.push(cur->left); // 左stk.push(cur); // 中stk.push(NULL); // 标记节点} else { // 遇到 NULL 标记,开始处理节点cur = stk.top(); // 取出被标记的待处理节点result.push_back(cur->val);stk.pop();}}return result;}
};

94. 二叉树的中序遍历

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode *> stk;if (root) stk.push(root);while ( !stk.empty() ) {TreeNode *cur = stk.top();stk.pop();if (cur) {if (cur->right) stk.push(cur->right); // 右stk.push(cur); // 中stk.push(NULL); // 标记if (cur->left) stk.push(cur->left); // 左} else {cur = stk.top();result.push_back(cur->val);stk.pop();}}return result;}
};

145. 二叉树的后序遍历

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode *> stk;if (root) stk.push(root);while ( !stk.empty() ) {TreeNode *cur = stk.top();stk.pop();if (cur) {stk.push(cur);stk.push(NULL);if (cur->right) stk.push(cur->right);if (cur->left) stk.push(cur->left); } else {cur = stk.top();result.push_back(cur->val);stk.pop();}}return result;}
};

相关文章:

随想录二刷Day15——二叉树

文章目录二叉树2. 递归遍历二叉树3. 二叉树的迭代遍历4. 二叉树的统一迭代法二叉树 2. 递归遍历二叉树 144. 二叉树的前序遍历 class Solution { public:vector<int> preorderTraversal(TreeNode* root) {vector<int> result;preorder(root, result);return res…...

docker-compose部署kafka服务时如何同时允许内外网访问?

背景 最近在学习kafka相关知识&#xff0c;需要搭建自己的kafka环境。综合考虑后决定使用docker-compose来管理维护这个环境。 docker-compose.yml Bitnami的yml文件就很不错&#xff0c;这里直接拿来用了。 version: "2"services:zookeeper:image: docker.io/bi…...

数据结构刷题(二十):17电话号码的字母组合、39组合总和、40组合总和II

一、电话号码的字母组合题目链接思路&#xff1a;回溯三部曲。确定回溯函数参数&#xff1a;题目中给的 digits&#xff0c;还要有一个参数就是int型的index&#xff08;记录遍历第几个数字&#xff0c;就是用来遍历digits的&#xff0c;同时也代表了递归的深度&#xff09;&am…...

Java面试总结(五)

sleep() 方法和 wait() 方法对比 相同点 两者都可以暂停线程的执行&#xff1b;两者都可以响应中断。 不同点 sleep()方法不会释放锁&#xff0c;wait()方法会释放锁&#xff1b; sleep()方法主要用于暂停线程的执行&#xff0c;wait()方法主要用于线程之间的交互/通信&…...

三维人脸实践:基于Face3D的渲染、生成与重构 <二>

face3d: Python tools for processing 3D face git code: https://github.com/yfeng95/face3d paper list: PaperWithCode 3DMM方法&#xff0c;基于平均人脸模型&#xff0c;可广泛用于基于关键点的人脸生成、位姿检测以及渲染等&#xff0c;能够快速实现人脸建模与渲染。推…...

在linux上部署Java项目

在Linux部署Java环境 要是想要部署java web程序,首先要配置环境 jdk tomcat mysql 安装jdk 推荐的方法是使用yum直接安装openjdk(开源的,与官方的jdk功能差不多),目前使用的最多的就是jdk8系列 yum list | grep jdk 在源上搜索所有关于jdk的文件 devel表示development的意思…...

线性表的接口

线性表的实现方式 顺序表 顺序表是一种线性表的实现方式&#xff0c;它是用一组地址连续的存储单元依次存储线性表中的数据元素&#xff0c;使得逻辑上相邻的元素在物理上也相邻⁴。顺序表可以用数组来实现&#xff0c;它的优点是可以快速定位第几个元素&#xff0c;但是缺点…...

spark三种操作模式的不同点分析

通常情况下,由于mapreduce计算引擎的效率问题,大部分公司使用的基本都是hive数仓spark计算引擎的方式搭建集群,所以对于spark的三种操作方式来进行简单的分析。在日常开发中&#xff0c;使用最多的方式取决于具体的需求和场景。以下是每种方式的一些常见用途&#xff1a;Spark …...

Vue3做出B站【bilibili】 Vue3+TypeScript【快速入门一篇文章精通系列(一)前端项目案例】

本项目分为二部分 1、后台管理系统&#xff08;用户管理&#xff0c;角色管理&#xff0c;视频管理等&#xff09; 2、客户端&#xff08;登录注册、发布视频&#xff09; Vue3做出B站【bilibili】 Vue3TypeScript【快速入门一篇文章精通系列&#xff08;一&#xff09;前端项目…...

猜数游戏--课后程序(Python程序开发案例教程-黑马程序员编著-第3章-课后作业)

实例10&#xff1a;猜数游戏 猜数游戏是一个古老的密码破译类、益智类小游戏&#xff0c;通常由两个人参与&#xff0c;一个人设置一个数字&#xff0c;一个人猜数字&#xff0c;当猜数字的人说出一个数字&#xff0c;由出数字的人告知是否猜中&#xff1a;若猜测的数字大于设…...

Nvidia jetson nano 部署yolov5_技术文档

Nvidia jetson nano 部署yolov5_技术文档 每天一句小姜格言&#xff1a;我行&#xff0c;我不是一般人儿 部署开始&#xff1a; 1、通过FileZilla&#xff0c;将window文件传输至jetson nano 上的nano文件夹下。 2、查看cuda 我买的jetson nano是带有配置好的镜像。系统配置…...

获取当前天数前N天

获取当前天数前N天 先封装到js里面 export const isTime (val) > {// 1.获取当前时间年月日时分秒格式xxxx-xx-xx xx:xx:xxvar myDate new Date() // 当前时间var y myDate.getFullYear() // 当前年份四位数var m myDate.getMonth() 1 < 10? 0 (myDate.getMont…...

Linux---基本指令

专栏&#xff1a;Linux 个人主页&#xff1a;HaiFan. 基本指令ls 指令pwd命令cd 指令touch指令mkdir指令&#xff08;重要&#xff09;rmdir指令 && rm 指令&#xff08;重要&#xff09;man指令&#xff08;重要&#xff09;cp指令&#xff08;重要&#xff09;mv指令…...

【UE4 RTS游戏】02-摄像机运动_完成摄像机在X轴上运动的相关步骤

效果通过控制键盘WS键使得“CameraPawn”进行前后移动步骤将landscape的Z轴位置更改为0删除“PostProcessVolume”将“LightmassImportanceVolume”移入Lighting文件夹内新建一个蓝图类&#xff0c;父类是Pawn&#xff0c;命名为“CameraPawn”将“MyController”重命名为“Cam…...

Kubernetes学习(五)持久化存储

Volume 卷 容器中的文件在磁盘上是临时存放的&#xff0c;这给容器中运行的特殊应用带来了一些问题。首先&#xff0c;当容器崩溃时&#xff0c;kubectl将重新启动容器&#xff0c;容器中的文件将会丢失--应为容器会以干净的状态重建。其次&#xff0c;当在一个Pod中运行多个容…...

下一个7年,保持期待、持续思考,酷雷曼继续向前!

过去7年&#xff0c;我们一直在思考&#xff0c; VR技术究竟能为我们的生活带来什么&#xff1f; 是足不出户就能云游千里的秀美风光&#xff1f; 是在家就能沉浸式体验线上消费的便利&#xff1f; 还是为商企和用户搭建更快速的沟通桥梁&#xff1f; NO.1、技术变革 在信…...

天梯赛训练L1-010--L1-012

目录 1、L1-010 比较大小 2、L1-011 A-B 3、L1-012 计算指数 4&#xff0c;一些题外话 1、L1-010 比较大小 分数 10 本题要求将输入的任意3个整数从小到大输出。 输入格式&#xff1a; 输入在一行中给出3个整数&#xff0c;其间以空格分隔。 输出格式&#xff1a; 在一…...

三分钟完成Stable Diffusion本地安装(零基础体验AI绘画)

三分钟完成Stable Diffusion本地安装前言安装步骤下载链接前言 最近AI绘画很火&#xff0c;很多无编程基础的小伙伴也想体验一下&#xff0c;所以写这篇博客来帮助小伙伴们愉快的体验一下~废话少说&#xff0c;我们直接开整&#xff01; 安装步骤 首先&#xff0c;下载本项目的…...

电子台账:教程目录及软件下载

前面内容有点杂乱&#xff0c;这里整理一下教程目录。重点是制作模板&#xff0c;企业只要学会适合自己的一种就行。如果这些模板都学会做了&#xff0c;那可以当老师了。1 目录1 模板制作之一——列过滤&#xff08;水平过滤&#xff09;2 模板制作之二——行过滤&#xff08;…...

多态的优势和弊端

目录 1.多态的优势 2.多态的弊端是什么&#xff1f; 3.引用数据类型的类型&#xff0c;转换有几种方式 4.强制类型转换能解决什么问题楠&#xff1f; 1.多态的优势 方法中&#xff0c;使用父类作为参数&#xff0c;可以接收所有子类的对象 package ploydemo3;import java.u…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

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

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

Web中间件--tomcat学习

Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机&#xff0c;它可以执行Java字节码。Java虚拟机是Java平台的一部分&#xff0c;Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...

HubSpot推出与ChatGPT的深度集成引发兴奋与担忧

上周三&#xff0c;HubSpot宣布已构建与ChatGPT的深度集成&#xff0c;这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋&#xff0c;但同时也存在一些关于数据安全的担忧。 许多网络声音声称&#xff0c;这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...

日常一水C

多态 言简意赅&#xff1a;就是一个对象面对同一事件时做出的不同反应 而之前的继承中说过&#xff0c;当子类和父类的函数名相同时&#xff0c;会隐藏父类的同名函数转而调用子类的同名函数&#xff0c;如果要调用父类的同名函数&#xff0c;那么就需要对父类进行引用&#…...

Scrapy-Redis分布式爬虫架构的可扩展性与容错性增强:基于微服务与容器化的解决方案

在大数据时代&#xff0c;海量数据的采集与处理成为企业和研究机构获取信息的关键环节。Scrapy-Redis作为一种经典的分布式爬虫架构&#xff0c;在处理大规模数据抓取任务时展现出强大的能力。然而&#xff0c;随着业务规模的不断扩大和数据抓取需求的日益复杂&#xff0c;传统…...