【二叉树】非递归实现前中后序遍历

news/2024/7/20 17:58:52/文章来源:https://blog.csdn.net/bit_pan/article/details/139251065

目录

前言

算法思想

非递归实现前序遍历

过程分析

代码

非递归实现中序遍历

过程分析

代码

非递归实现后序遍历

过程分析

代码


前言

1)前序: 左子树 右子树

2)中序:左子树 右子树

3)后序:左子树  右子树

可以看出,这三种遍历方式的本质区别在于什么时候访问根节点,下面将介绍一种很厉害的思想,对于前中后序的非递归实现,它可以是通解。

算法思想

将二叉树分割成两部分:

1)左路节点

2)左路节点的右子树

它的每一棵子树也可以继续分为左路节点和左路节点的右子树。

实现这种算法,我们需要借助一种数据结构——栈,同时,为了存储数据我们还需要借助另一种数据结构——vector。

 下面,把这种算法转换成代码。

非递归实现前序遍历

过程分析

以这棵树为例:

1)所有左路节点进栈。

2)根据前序遍历的规则,所遍历到的结点都可以直接反问,即可以直接保存进vector中, 因为每个节点都可以是根。

3)左路结点遍历完后,出栈,在出栈时,如果它的右子树不为空,则将它的右子树的左路节点入栈,重复此操作,就可以遍历完左路节点对应        的右子树。

以上图为例:

所有左路节点进栈(面向屏幕右手边为栈顶):

stack:8  3  1 

vector:8  3  1

考虑1出栈,考虑到1的右子树为空,所以可以直接出栈。下面更新stack和vector。

stack:8  3

vector:8  3  1

考虑3出栈,考虑到3的右子树不为空,所以3出栈后,要把3的右子树的左路节点6和4依次入栈(结点3会有记录,不会找不到它的右树)。下面更新stack和vector。

stack:8  6  4

vector:8  3  1  6  4

考虑4出栈,考虑到4的右树为空,可以直接出栈。下面更新stack和vector。

stack:8  6 

vector:8  3  1  6  4

考虑6出栈,考虑到6的右子树不为空,所以出栈后,它的右子树的左路节点7要入栈。下面更新stack和vector。

stack:8  7

vector:8  3  1  6  4  7

考虑7出栈,考虑到7的右子树为空,所以可以直接出栈。下面更新stack和vector。

stack:8  

vector:8  3  1  6  4  7

考虑8出栈,考虑到8的右子树不为空,所以出栈后,它的右子树的左路节点10要入栈。下面更新stack和vector。

stack:10  

vector:8  3  1  6  4  7  10

考虑10出栈,考虑到10的右子树为空,所以可以直接出栈。下面更新stack和vector。

stack:空 

vector:8  3  1  6  4  7  10

此时,栈已空,所有结点均已访问完毕,前序遍历结束。

代码

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> ret;TreeNode* cur = root;while(cur || !st.empty()){//所有左路节点入栈while(cur){ret.push_back(cur->val);//遍历到的结点可直接访问st.push(cur);cur = cur->left;}TreeNode* top = st.top();//访问当前节点的右子树,如果不为空,会进入内层的while循环,把它的左路节点入栈//如果为空,则不会进入内存while循环cur = top->right;st.pop();}return ret;}
};

非递归实现中序遍历

过程分析

中序遍历和前序遍历尤为相似,它们的本质区别在于什么时候访问根结点。

1)所有左路节点进栈

2)左路节点进栈的同时不能去访问这些节点,因为根据中序遍历的规则,应该先访问左子树(这就是与前序遍历的区别)

3)所有左路节点都进栈以后,意味着最后一个左路节点的左子树(为空)已经访问完毕,可以访问根了,这时,弹出栈顶元素,并把它的值存       储进vector中,如果它有右子树,还应该把它的右子树的左路节点入栈。

代码

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> v;TreeNode* cur = root;while(cur || !st.empty()){//左路节点入栈while(cur){st.push(cur);cur = cur->left;}//退出循环后,意味着左路节点已访问,可以访问根了TreeNode* top = st.top();v.push_back(top->val);//访问根st.pop();cur = top->right;//左路节点的右子树如果非空,则让它的左路节点入栈}return v;}
};

非递归实现后序遍历

过程分析

后序遍历和前面的两种遍历方式其实差不多,都是把整棵树分为左路节点和左路节点的右子树。关键问题在于什么时候访问根。

1)左路节点进栈

2)左路节点进栈是不能直接去访问,根据后序遍历的规则,应该是先访问左子树,右子树再到根。

3)左路节点进栈完毕,意味着可以访问右子树了,如果左路节点的右子树不为空,就让它的左路节点进栈,如果为空,就可以访问根结点了

4)访问完左节点后,如果当前栈顶结点的右子树为空或者上一个访问的结点是它的右节点,满足这两个条件之一就可以访问当前节点了(根)

以上图为例 

所有左路节点进栈(面向屏幕右手边为栈顶):

stack:8  3  1 

vector:空

考虑1出栈,考虑到1的右子树为空,所以可以访问根即节点1,且1出栈。下面更新stack和vector。

stack:8  3

vector:1

考虑3出栈,考虑到3的右子树不为空,且上一个访问的节点不是它的右节点,所以3还不能访问,也还不可以出栈,要把3的右子树的左路节点6和4依次入栈 。下面更新stack和vector。

stack:8  3  6  4

vector:1

考虑4出栈,考虑到4的右树为空,可以直接出栈并访问该节点。下面更新stack和vector。

stack:8  3  6 

vector:1  4

考虑6出栈,考虑到6的右子树不为空且上一个访问的结点不是它的右节点,所以不能出栈,将它的右子树的左路节点7要入栈。下面更新stack和vector。

stack:8  3  6  7

vector:1  4

这里对节点6进行了第一次判断。

考虑7出栈,考虑到7的右子树为空,所以可以直接出栈并访问。下面更新stack和vector。

stack:8  3  6 

vector:1  4  7

考虑6出栈,考虑到6的右结点(7)为上一个访问的结点,所以可以访问6并将6弹出栈。下面更新stack和vector。

stack:8  3

vector:1  4  7  6

这里对节点6进行了第二次判断。可以看出,记录上一个访问的结点是有意义的。

考虑3出栈,考虑到3的右节点(6)为上一个访问的结点,所以可以访问3并弹出栈。下面更新stack和vector。

stack:8

vector:1  4  7  6  3

考虑8出栈,8的右子树不为空且它的右节点(10)不是上一个访问的结点,所以8还不可以出栈,应该将10入栈。下面更新stack和vector。

stack:8  10

vector:1  4  7  6  3

考虑10出栈,10的右树为空,可以访问,并弹出栈。下面更新stack和vector。

stack:8  

vector:1  4  7  6  3  10

考虑8出栈,考虑到上一个访问的结点10为8的右节点,所以8可以访问并弹出栈。下面更新stack和vector。

stack:空 

vector:1  4  7  6  3  10  8

此时,栈已空,所有结点均已访问完毕,后序遍历结束。

代码

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> v;TreeNode* cur = root, *prev = nullptr;while(cur || !st.empty()){//左路节点入栈while(cur){st.push(cur);cur = cur->left;}TreeNode* top = st.top();if(top->right == nullptr || prev == top->right){//访问当前结点v.push_back(top->val);//更新prevprev = top;st.pop();}else{//右树的左路节点入栈cur = top->right;}}return v;}
};

完~

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_1052960.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

3W 1.5KVDC、3KVDC 隔离,宽电压输入 DC/DC 电源模块——TP03DA 系列

TP03DA系列电源模块额定输出功率为3W&#xff0c;外形尺寸为31.75*20.32*10.65&#xff0c;应用于2:1及4:1宽电压输入范围 4.5-9V、9V-18V、18V-36V、36V-72V、9V-36V和18-72VDC的输入电压环境&#xff0c;输出电压精度可达1%&#xff0c;具有输出短路保护等功能&#xff0c;可…

室内也可以用北斗定位?还能用RTK?

室内卫星顾名思义&#xff0c;就是在室内有遮挡环境中的卫星定位技术&#xff0c;众所周知&#xff0c;目前全球几大GNSS定位系统已经很完善&#xff0c;但是GNSS有个致命的弱点&#xff0c;就是地面如果有遮挡就没有信号&#xff0c;在这样的条件下&#xff0c;在室内定位场景…

结合Django和Vue.js构建现代Web应用

文章目录 1. 创建Django项目2. 配置Django后端3. 创建Vue.js前端4. 连接Django和Vue.js5. 构建和部署 在现代Web开发中&#xff0c;结合后端框架和前端框架是非常常见的&#xff0c;其中Django作为一种流行的Python后端框架&#xff0c;而Vue.js则是一种灵活强大的前端框架。本…

Pyinstaller打包exe文件解决指南

打包命令 打包 Python 文件 输入如下格式的命令即可 默认命令 Pyinstaller 文件名.py Pyinstaller -option1 -option2 -... 要打包的文件 Pyinstaller 文件名.pyPyinstaller -option1 -option2 -... 要打包的文件 参数选项比较多&#xff0c;这里我列一个表&#xff1a;…

新V 系首批订单交付!苏州金龙助新疆游骏文旅集团打造旅运新标杆

热播剧集《我的阿勒泰》收官不久&#xff0c;6月新疆旅游旺季将至。 2024年5月下旬&#xff0c;苏州金龙海格客车新V系首批30辆正式交付新疆客户&#xff01; 作为苏州金龙海格客车新V系首批用户&#xff0c;新疆游骏文旅集团董事长王红强表示&#xff1a;“海格新V系从外观、…

【JavaEE精炼宝库】多线程(3)线程安全 | synchronized

目录 一、线程安全 1.1 经典线程不安全案例&#xff1a; 1.2 线程安全的概念&#xff1a; 1.3 线程不安全的原因&#xff1a; 1.3.1 案例刨析: 1.3.2 线程不安全的名词解释&#xff1a; 1.3.3 Java 内存模型 (JMM)&#xff1a; 1.3.4 解决线程不安全问题&#xff1a; 二…

Python代码:十七、生成列表

1、题目 描述&#xff1a; 一串连续的数据用什么记录最合适&#xff0c;牛牛认为在Python中非列表&#xff08;list&#xff09;莫属了。现输入牛牛朋友们的名字&#xff0c;请使用list函数与split函数将它们封装成列表&#xff0c;再整个输出列表。 输入描述&#xff1a; …

第十三周 5.27面向对象的三大特性(封装、继承、多态)(三)

3.instanceof避免类型转换异常: (1)语法:引用名 instanceof 类名 (2)执行:判断引用中存储的实际对象类型是否兼容于后面的类型(是否为后面类型的一种)&#xff0c;兼容一true&#xff0c;不兼容—false (3)作用:可以在程序设计中避免类型转换异常 直接使用案例…

工程机械比例阀电流采集方案——IPEhub2与IPEmotion APP

自从国家实施一带一路和新基建计划以来&#xff0c;工程机械的需求量呈现出快速增长的趋势。而关于工程机械&#xff0c;其比例阀的控制问题不容忽视。比例阀是一种新型的液压控制装置——在普通压力阀、流量阀和方向阀上&#xff0c;用比例电磁铁替代原有的控制部分&#xff0…

微服务-Nacos-安装-集成SpringBoot

微服务-SpringCloud-ALibaba-Nacos Nacos 是阿里巴巴推出的 SpringCloud的组件 官网:什么是 Nacos 主要是为了解决微服务的架构中 服务治理的问题服务治理就是进行服务的自动化管理&#xff0c;其核心是服务的注册与发现。 服务注册&#xff1a;服务实例将自身服务信息注册…

uni-app 微信 支付宝 小程序 使用 longpress 实现长按删除功能,非常简单 只需两步

1、先看效果 2、直接上代码 ui结构 <view class"bind" longpress"deleteImage" :data-index"index"><view class"bind_left">绑定设备</view><view class"bind_right"><view class"bind_t…

JMeter 测试单节点与集群的并发异常率

一. JMeter 测试单节点与集群的并发异常率 下载地址&#xff1a;https://jmeter.apache.org/download_jmeter.cgi 单个tomcat测试结果(2000个用户&#xff0c;每个用户访问100次) nginx集群负载均衡tomcat结果(2000个用户&#xff0c;每个用户访问100次)

Go 实现 WebSocket 的双向通信

在Go语言中实现WebSocket的双向通信通常需要使用第三方库&#xff0c;其中 gorilla/websocket 是一个非常流行和广泛使用的库。 1、安装 go get github.com/gorilla/websocket 2、编写WebSocket服务器代码 package mainimport ("fmt""github.com/gorilla/we…

金蝶云星空与旺店通·企业版对接集成采购入库查询打通创建采购入库单

金蝶云星空与旺店通企业版对接集成采购入库查询打通创建采购入库单 数据源系统:金蝶云星空 金蝶K/3Cloud&#xff08;金蝶云星空&#xff09;是移动互联网时代的新型ERP&#xff0c;是基于WEB2.0与云技术的新时代企业管理服务平台。金蝶K/3Cloud围绕着“生态、人人、体验”&…

代码随想录算法训练营第21天|● 530.二叉搜索树的最小绝对差 ● 501.二叉搜索树中的众数 ● 236. 二叉树的最近公共祖先

二叉搜索树的最小绝对差 题目连接 https://leetcode.cn/problems/minimum-absolute-difference-in-bst/ 思路&#xff1a; 利用二叉搜索树的中序遍历的特性&#xff0c;将二叉树转成有序数组&#xff0c;进而求任意两个数的最小绝对差。 代码 /*** Definition for a bina…

MFC密码对话框之间数据传送实例(源码下载)

新建一个login工程项目对话框&#xff0c;主对话框IDD_LOGIN_DIALOG中一个显示按钮IDC_BUTTON1、一个密码按钮IDC_BUTTON2。添加一个密码对话框IDD_DIALOG1&#xff0c;添加类password&#xff0c;在对话框中添加一个编辑框IDC_EDIT1、一个确定按钮IDC_BUTTON1。 程序功能&…

记一次攻防演练中的若依(thymeleaf 模板注入)getshell

记一次攻防演练中幸运的从若依弱口令到后台getshell的过程和分析。 0x01 漏洞发现 首先我会先把目标的二级域名拿去使用搜索引擎来搜索所用的搜索引擎收集到包含这个目标二级域名的三级域名或者四级域名的网站。 这样子可以快速的定位到你所要测试的漏洞资产。 1、推荐三个…

新能源汽车为乙炔炭黑行业带来了发展机遇

新能源汽车为乙炔炭黑行业带来了发展机遇 乙炔炭黑&#xff08;Acetylene carbon black&#xff09;又称乙炔黑&#xff0c;外观为黑色极细粉末&#xff0c;相对密度1.95&#xff08;氮置换法&#xff09;&#xff0c;纯度很高&#xff0c;含碳量大于99.5%&#xff0c;氢含量小…

微信小程序实现容器图片流式布局功能,配合小程序原生框架使用。

小程序实现容器图片流式布局功能&#xff0c;因为目前论坛上也有很多博主出过类似的文章&#xff0c;这里我就以一个小白角度去讲一下如何实现的吧。给作者一点点鼓励&#xff0c;先点个赞赞吧&#x1f44d;&#xff0c;蟹蟹&#xff01;&#xff01; 目标 实现下方效果图 技术…

【Sql Server】随机查询一条表记录,并重重温回顾下自定义函数的封装和使用

大家好&#xff0c;我是全栈小5&#xff0c;欢迎来到《小5讲堂》。 这是《Sql Server》系列文章&#xff0c;每篇文章将以博主理解的角度展开讲解。 温馨提示&#xff1a;博主能力有限&#xff0c;理解水平有限&#xff0c;若有不对之处望指正&#xff01; 目录 前言随机查询语…