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

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

渲染学进阶内容——模型

最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

力扣热题100 k个一组反转链表题解

题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...

GO协程(Goroutine)问题总结

在使用Go语言来编写代码时&#xff0c;遇到的一些问题总结一下 [参考文档]&#xff1a;https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现&#xff1a; 今天在看到这个教程的时候&#xff0c;在自己的电…...

comfyui 工作流中 图生视频 如何增加视频的长度到5秒

comfyUI 工作流怎么可以生成更长的视频。除了硬件显存要求之外还有别的方法吗&#xff1f; 在ComfyUI中实现图生视频并延长到5秒&#xff0c;需要结合多个扩展和技巧。以下是完整解决方案&#xff1a; 核心工作流配置&#xff08;24fps下5秒120帧&#xff09; #mermaid-svg-yP…...

在RK3588上搭建ROS1环境:创建节点与数据可视化实战指南

在RK3588上搭建ROS1环境:创建节点与数据可视化实战指南 背景介绍完整操作步骤1. 创建Docker容器环境2. 验证GUI显示功能3. 安装ROS Noetic4. 配置环境变量5. 创建ROS节点(小球运动模拟)6. 配置RVIZ默认视图7. 创建启动脚本8. 运行可视化系统效果展示与交互技术解析ROS节点通…...

简单介绍C++中 string与wstring

在C中&#xff0c;string和wstring是两种用于处理不同字符编码的字符串类型&#xff0c;分别基于char和wchar_t字符类型。以下是它们的详细说明和对比&#xff1a; 1. 基础定义 string 类型&#xff1a;std::string 字符类型&#xff1a;char&#xff08;通常为8位&#xff09…...

HTML中各种标签的作用

一、HTML文件主要标签结构及说明 1. <&#xff01;DOCTYPE html> 作用&#xff1a;声明文档类型&#xff0c;告知浏览器这是 HTML5 文档。 必须&#xff1a;是。 2. <html lang“zh”>. </html> 作用&#xff1a;包裹整个网页内容&#xff0c;lang"z…...

基于 HTTP 的单向流式通信协议SSE详解

SSE&#xff08;Server-Sent Events&#xff09;详解 &#x1f9e0; 什么是 SSE&#xff1f; SSE&#xff08;Server-Sent Events&#xff09; 是 HTML5 标准中定义的一种通信机制&#xff0c;它允许服务器主动将事件推送给客户端&#xff08;浏览器&#xff09;。与传统的 H…...

npm安装electron下载太慢,导致报错

npm安装electron下载太慢&#xff0c;导致报错 背景 想学习electron框架做个桌面应用&#xff0c;卡在了安装依赖&#xff08;无语了&#xff09;。。。一开始以为node版本或者npm版本太低问题&#xff0c;调整版本后还是报错。偶尔执行install命令后&#xff0c;可以开始下载…...