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

【C++】二叉树的非递归遍历

非递归遍历二叉树

  • 一、二叉树的前序遍历
  • 二、二叉树的中序遍历
  • 三、二叉树的后序遍历
    • 3.1 方法一
    • 3.2 方法二

一、二叉树的前序遍历

题目链接

我们可以把任何一棵树看成左路节点,左路节点和右子树。先访问左路节点,再访问左路节点的右子树。在右子树中也重复这种循环,就是非递归遍历二叉树的思想。

在这里插入图片描述
解释:
栈st存放节点,v存放数值,cur初始化为root。
循环条件是栈不为空或者cur不为空(访问最后一个节点之前栈就已经为空了),循环遍历左子树并且把左子树入栈,同时把值存入v中。然后弹出栈顶元素,并且把栈顶元素的右子树赋值给cur,这样就形成了遍历。
当栈不为空的时候说明还有左路节点的右子树没有被访问,当cur不为空的时候说明还有树要被访问。当同时为空的时候才是访问完成。当一个节点出栈的时候说明此时该节点及该节点的左子树已经被访问完成了。

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> v;TreeNode* cur = root;while(cur || !st.empty()){while(cur){st.push(cur);v.push_back(cur->val);cur = cur->left;}TreeNode* node = st.top();st.pop();cur = node->right;// 转化成子问题访问右子树}return v;}
};

二、二叉树的中序遍历

题目链接

因为中序遍历的访问顺序是左根右,跟前序遍历不同,所以我们让左节点入栈的时候先不访问,出栈(说明左子树访问完了)时在访问节点

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> v;stack<TreeNode*> st;TreeNode* cur = root;while(!st.empty() || cur){while(cur){st.push(cur);cur = cur->left;}TreeNode* node = st.top();st.pop();v.push_back(node->val);cur = node->right;}return v;}
};

三、二叉树的后序遍历

3.1 方法一

首先我们知道后序遍历就是左右根,而我们可以把访问顺序变成根右左,然后再逆置顺序。而根右左就跟前序遍历的方法一样:

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> v;TreeNode* cur = root;while(cur || !st.empty()){while(cur){st.push(cur);v.push_back(cur->val);cur = cur->right;}TreeNode* node = st.top();st.pop();cur = node->left;}reverse(v.begin(), v.end());return v;}
};

3.2 方法二

按照常规的遍历方法走左右根,但是这里有一个问题:
当访问到根的时候有两种情况:
1️⃣ 从左子树回来,现在要先访问右子树
2️⃣ 从右子树回来,左右子树已经访问完毕,再访问根。
针对这种情况我们可以在加一个变量来确定是第几次访问根,如果是第一次就访问右子树,如果是第二次就访问。

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {stack<pair<TreeNode*, bool>> st;vector<int> v;TreeNode* cur = root;while(cur || !st.empty()){while(cur){st.push(make_pair(cur, false));cur = cur->left;}TreeNode* node = st.top().first;if(st.top().second == true){st.pop();v.push_back(node->val);}else{st.top().second = true;cur = node->right;}}return v;}
};

相关文章:

【C++】二叉树的非递归遍历

非递归遍历二叉树一、二叉树的前序遍历二、二叉树的中序遍历三、二叉树的后序遍历3.1 方法一3.2 方法二一、二叉树的前序遍历 题目链接 我们可以把任何一棵树看成左路节点&#xff0c;左路节点和右子树。先访问左路节点&#xff0c;再访问左路节点的右子树。在右子树中也重复这…...

Linux——线程同步(条件变量、POSIX信号量)和线程池

一.线程同步&#xff08;一&#xff09;.概念线程同步是一种多线程关系&#xff0c;指的是线程之间按照特定顺序访问临界资源&#xff0c;进而能够避免线程饥饿问题。所谓线程饥饿指的是某个线程长期“霸占”临界资源&#xff0c;导致其他线程无法访问该资源。而通过线程同步机…...

leaflet 上传CSV文件,导出geojson格式文件(064)

第064个 点击查看专栏目录 本示例的目的是介绍演示如何在vue+leaflet中加载CSV文件,将图形显示在地图上。点击导出geojson,下载成geojson文件。 直接复制下面的 vue+openlayers源代码,操作2分钟即可运行实现效果. 文章目录 示例效果配置方式示例源代码(共114行)安装插件…...

Java内部类

文章目录一、内部类的概念二、内部类的分析三、内部类的分类1. 成员内部类2. 静态内部类3. 局部内部类4. 匿名内部类匿名内部类与Lambda表达式一、内部类的概念 在 Java 中&#xff0c;可以将一个类定义在另一个类里面或者一个方法里面&#xff0c;这样的类称为内部类。内部类…...

Centos系统里运行java的jar包

目前使用springboot开发是嵌入方式的tomcat&#xff0c;不需要单独使用tomcat&#xff0c;那么经常在服务器上运行jar包&#xff0c;这里记录一下在centos7系统里运行jar的方式。在运行之前需要确定centos7系统是否安装了java环境以及配置环境变量&#xff0c;还有jar需要运行的…...

招标采购流程的电子招标采购,是管理复杂供应链和多层供应商的高效方式。

负载均衡&#xff08;Load Balance&#xff09; 由于目前现有网络的各个核心部分随着业务量的提高&#xff0c;访问量和数据流量的快速增长&#xff0c;其处理能力和计算强度也相应地增大&#xff0c;使得单一的服务器设备根本无法承担。在此情况下&#xff0c;如果扔掉现有设…...

【C语言】C程序结构和基本语法

1、C语言程序结构 我们学习一门编程语言&#xff0c;第一个实例都是"hello world!"&#xff0c;下面看一个最简单的C程序结构。 #include <stdio.h>int main() {/* 我的第一个 C 程序 */printf("Hello, World! \n");return 0; }程序的第一行 #incl…...

YOLOv8 目标检测 | 自定义数据集

本文介绍了使用用于目标检测的自定义数据训练 YOLOv8 模型。我正在使用来自 kaggle 的 yolo 格式的“Face Mask Dataset”&#xff0c;数据集链接如下&#xff1a;https://www.kaggle.com/datasets/maalialharbi/face-mask-dataset?resourcedownloadYOLOv8 是目前最先进的 YOL…...

Lua语法入门

注意&#xff1a;文章将持续更新完善 文章目录一. 初识Lua二. HelloWorld三. Lua的数据类型四. 变量五. 循环六. 函数七. 条件控制一. 初识Lua Lua 是一种轻量小巧的脚本语言&#xff0c;用标准C语言编写并以源代码形式开放&#xff0c; 其设计目的是为了嵌入应用程序中&#…...

华为OD机试真题JAVA实现【最小步骤数】真题+解题思路+代码(20222023)

🔥系列专栏 华为OD机试(JAVA)真题目录汇总华为OD机试(Python)真题目录汇总华为OD机试(C++)真题目录汇总华为OD机试(JavaScript)真题目录汇总文章目录 🔥系列专栏题目输入输出示例一输入输出说明示例二输入输出解题思路...

预检请求OPTIONS

这里写目录标题简单请求和非简单请求简单请求非简单请求预检请求OPTIONS简单请求和非简单请求 浏览器将请求分为两大类&#xff1a;简单请求&#xff08;simple request&#xff09;和非简单请求&#xff08;not-so-simple request&#xff09; 简单请求 简单请求&#xff0…...

引入短信服务发送手机验证码进行安全校验

其他方案>引入QQ邮箱发送验证码进行安全校验 相对短信验证码&#xff0c;操作更简单而且免费 最近想给自己的项目在注册时加点安全校验&#xff0c;准备使用免费的邮箱验证来着&#xff0c;在上一篇引入QQ邮箱进行安全校验时&#xff0c;看有朋友说阿里云会送一些短信服务免…...

opencv绘制直线

大家好&#xff0c;我是csdn的博主&#xff1a;lqj_本人 这是我的个人博客主页&#xff1a; lqj_本人的博客_CSDN博客-微信小程序,前端,python领域博主lqj_本人擅长微信小程序,前端,python,等方面的知识https://blog.csdn.net/lbcyllqj?spm1011.2415.3001.5343哔哩哔哩欢迎关注…...

Seata源码学习(五)- Seata服务端(TC)源码解读

Seata源码分析- Seata服务端&#xff08;TC&#xff09;源码解读 上节课我们已经分析到了SQL语句最终的执行器&#xff0c;但是再往下分析之前&#xff0c;我们需要先来分析一下TM客户端与TC端通讯以后&#xff0c;TC端的具体操作 服务端表解释 我们的Seata服务端在应用的时…...

低版本jQuery导致XSS Nuclei FUZZ POC

目录 1.前言 2. Nuclei FUZZ jQuery XSS POC 3.漏洞验证 4.修复建议 1.前言 我记得以前用那些漏扫工具时时常会报一个低版本jQuery的安全问题,当时还不会验证。直到有一天,它托梦给我。我悟了。低版本jQuery导致XSS POC文件文末获取。...

【Linux】进程的描述组织与进程状态

文章目录&#x1f3aa; 进程的描述组织&#x1f680;1.什么是进程&#x1f680;2.进程的形成&#x1f680;3.进程标识符 *⭐3.1 PS命令查看PID⭐3.2 /proc目录查看进程属性&#x1f680;4.父子进程⭐4.1 系统调用获取PID⭐4.2 fork创建子进程⭐4.3 fork双返回值问题⭐4.4 写时拷…...

8.2.1.1 WHERE 子句优化

本节讨论可用于处理 WHERE 子句的优化。示例使用 SELECT 语句&#xff0c;但相同的优化适用于 DELETE 和 UPDATE 语句中的 WHERE 子句。 注意 因为 MySQL 优化器的工作正在进行&#xff0c;所以这里并没有记录 MySQL 执行的所有优化。 您可能会尝试重写查询以使算术运算更快&am…...

拆个微波炉,分析一下电路

微波炉是用2450MHz的超高频电磁波来加热食品&#xff0c;它能无损穿越塑料&#xff0c;陶瓷&#xff0c;不能穿越金属&#xff0c;碰到金属会反射&#xff0c;但穿过含水食物&#xff0c;食物内的分子会高速摩擦&#xff0c;产生热量&#xff0c;使食物变熟。在厨房电器中&…...

DM8:DMDSC共享存储集群搭建-共享存储绑定

DM8:DMDSC共享存储集群搭建-共享存储绑定环境介绍&#xff1a;1 发现共享磁盘2 对共享存储进行分区格式化2.1 格式化成功但不可用2.2 解决问题修改错误的分区格式3 配置/etc/rc.d/rc.local3.1 编辑文件&#xff08;两个节点配置相同&#xff09;3.2 使rc.local生效4 重启操作系…...

Spark OOM问题常见解决方式

文章目录Spark OOM问题常见解决方式1.map过程产生大量对象导致内存溢出2.数据不平衡导致内存溢出3.coalesce调用导致内存溢出4.shuffle后内存溢出5. standalone模式下资源分配不均匀导致内存溢出6.在RDD中&#xff0c;共用对象能够减少OOM的情况优化1.使用mapPartitions代替大部…...

铭豹扩展坞 USB转网口 突然无法识别解决方法

当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

vue3 字体颜色设置的多种方式

在Vue 3中设置字体颜色可以通过多种方式实现&#xff0c;这取决于你是想在组件内部直接设置&#xff0c;还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法&#xff1a; 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

R语言速释制剂QBD解决方案之三

本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...

二维FDTD算法仿真

二维FDTD算法仿真&#xff0c;并带完全匹配层&#xff0c;输入波形为高斯波、平面波 FDTD_二维/FDTD.zip , 6075 FDTD_二维/FDTD_31.m , 1029 FDTD_二维/FDTD_32.m , 2806 FDTD_二维/FDTD_33.m , 3782 FDTD_二维/FDTD_34.m , 4182 FDTD_二维/FDTD_35.m , 4793...

倒装芯片凸点成型工艺

UBM&#xff08;Under Bump Metallization&#xff09;与Bump&#xff08;焊球&#xff09;形成工艺流程。我们可以将整张流程图分为三大阶段来理解&#xff1a; &#x1f527; 一、UBM&#xff08;Under Bump Metallization&#xff09;工艺流程&#xff08;黄色区域&#xff…...

内窥镜检查中基于提示的息肉分割|文献速递-深度学习医疗AI最新文献

Title 题目 Prompt-based polyp segmentation during endoscopy 内窥镜检查中基于提示的息肉分割 01 文献速递介绍 以下是对这段英文内容的中文翻译&#xff1a; ### 胃肠道癌症的发病率呈上升趋势&#xff0c;且有年轻化倾向&#xff08;Bray等人&#xff0c;2018&#x…...

背包问题双雄:01 背包与完全背包详解(Java 实现)

一、背包问题概述 背包问题是动态规划领域的经典问题&#xff0c;其核心在于如何在有限容量的背包中选择物品&#xff0c;使得总价值最大化。根据物品选择规则的不同&#xff0c;主要分为两类&#xff1a; 01 背包&#xff1a;每件物品最多选 1 次&#xff08;选或不选&#…...