二叉树前序中序后序遍历(非递归)

大家好,又和大家见面啦!今天我们一起去看一下二叉树的前序中序后序的遍历,相信这个对大家来说是信手拈来,但是,今天我们并不是使用常见的递归方式来解题,我们采用迭代方式解答。我们先看第一道前序遍历 

1、前序遍历

二叉树的前序遍历

前序遍历是先将二叉树的根节点遍历,再遍历左子树、右子树。我们做这道题的思想是把二叉树划分为两部分,一是左路节点,二是左路节点的右子树。什么是左路节点,如上图的二叉树来说,

这就算以8为根节点的二叉树的左路节点,也就是以8为根节点,它的左孩子的左孩子的左孩子......这一条路径。我们先让左路节点入栈,因为是前序遍历,所以我们入栈的同时,遍历当前结点的val,当左路结点都入栈完,那么当前节点一定是没有左子树的,我们让这个结点出栈,这个时候我们处理当前结点的右子树,右子树同样进行先让左路节点入栈.....循环做此操作,直到右子树也会空,然后将这个结点的所有左右子树我们都访问完成,我们已经pop掉这个时候,只需要处理新的栈顶元素就可以啦。

话不多说,思路就是这个样子,下面把代码写出来让大家看看。

定义一个cur从根节点开始,然后定义一个栈存储左路结点,一个vector存储左路节点的数据。

vector<int> preorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> v;TreeNode* cur=root;//cur从根节点开始while(cur){while(cur){v.push_back(cur->val);st.push(cur);//左路结点入栈cur=cur->left;}//处理栈内的右子树TreeNode* top=st.top();st.pop();cur=top->right;//处理左路节点的右子树}return v;}

代码写起来很简单,但是我们会发现这个提交是过不了的,为什么呢?大家看,我们在把1的右节点赋给cur去处理1的右子树时,结点1是没有右结点的,这个时候cur为空,上面这个大循环就进不去,而这个时候,我们其它的左路节点都还在栈里面没有处理,所以,外面这个大循环的判断条件是不正确的。应该改成

while(cur||!st.empty())

当栈不为空的时候,我们也要处理。 然后我们再运行,就可以通过了。

2、中序遍历

二叉树的中序遍历

我们还是拿这棵树来看,其实中序和前序思路是完全一样,只不过前序的遍历顺序是根左右,我们左路结点入栈的时候就可以直接访问其val,但是中序遍历的顺序是左根右,所以我们写中序的时候应该把访问val的顺序调到结点出栈的时候访问就可啦。

下面我们开始实现

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;}

3、后序遍历

二叉树的后序遍历

后序遍历的遍历顺序是左右根,我们只有把左右结点全部访问完成才能访问根节点的数据,或者左右节点为空才能直接访问根节点的数据。左节点我们在左路子树入栈的时候就算是访问,但是右节点怎么解决呢?

所以说,我们这里需要解决一下,怎么才能知道右节点已经访问过了。我们以这里的结点6为例,要访问结点6的val,首先,我们把8,3,1入栈,结点1没有右子树,可以直接获取它的val,出栈后,栈顶元素是3,3有右子树,需要先处理它的右树,,然后6,4入栈,这时栈顶结点为4,4没有右树,直接获取它的val,此时栈顶元素为6,6他有右树,需要先处理他的右树,此时结点7入栈,这个时候7没有右树,直接获取它的val,这个时候结点6的左右树都访问完毕,可以访问6的val了,但是我们怎么判断结点6的左右树都已经访问完毕了呢?结点6上一次访问的结点是7,我们只需要判断,6结点的上一次访问的结点是不是7就可以了。

我们可以定义一个结点prev,每访问完一个栈顶元素,我们就把top赋给prev,表示上一个访问结点,我们只需要判断top->right==prev,即我们已经访问过top->right这个结点就行了,这样我们可以直接获取栈顶的val值。

因此,只有在当前结点的右树为空,或者当前结点的右结点是我们上一次访问的结点,我们就可以获取它的val值。

下面我们开始写代码

vector<int> postorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> v;TreeNode* cur=root;TreeNode* prev=nullptr;while(cur||!st.empty()){while(cur){st.push(cur);cur=cur->left;}TreeNode* top=st.top();//分情况讨论,如果当前这个结点的右子树为空,或者当前结点的右子树是我们上次访问的结点;表示我们已经访问过它的子树,就可以直接获取当前结点的valif(top->right==nullptr||top->right==prev){st.pop();v.push_back(top->val);prev=top;}//否者,访问这个结点的右树else{cur=top->right;}}return v;

到这里,二叉树的前序中序后序三个非递归方式就讲解完毕啦。我们下次再见呀

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

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

相关文章

前端秘法进阶篇----这还是我们熟悉的浏览器吗?(浏览器的渲染原理)

目录 一.浏览器渲染原理 二.渲染时间点 三.渲染流水线 1.解析html(Parse HTML) 1.1解析成DOM树(document object model) 1.2解析成CSSOM树(css object model) 2.样式计算(Recalculate Style) 3.布局(Layout) 4.分层(Layer) 5. 绘制(Paint) 6.分块(Tiling) 7. 光栅化…

第13章 网络 Page724 asio定时器

程序代码&#xff1a; 11行&#xff0c;声明一个ios对象 13行&#xff0c;使用ios对象作为参数声明一个定时器&#xff0c;此时&#xff0c;定时器和ios完成了关联&#xff0c;后面定时器如果有任务的话&#xff0c;就可以将任务交给ios 16行&#xff0c;为定时器设置一个定…

【图像分割 2024 ICLR】Conv-LoRA

【图像分割 2024 ICLR】Conv-LoRA 论文题目&#xff1a;CONVOLUTION MEETS LORA: PARAMETER EFFICIENT FINETUNING FOR SEGMENT ANYTHING MODEL 中文题目&#xff1a;卷积满足lora:分段任意模型的参数有效微调 论文链接&#xff1a;https://arxiv.org/abs/2401.17868 论文代码&…

C++数据结构与算法——栈与队列

C第二阶段——数据结构和算法&#xff0c;之前学过一点点数据结构&#xff0c;当时是基于Python来学习的&#xff0c;现在基于C查漏补缺&#xff0c;尤其是树的部分。这一部分计划一个月&#xff0c;主要利用代码随想录来学习&#xff0c;刷题使用力扣网站&#xff0c;不定时更…

简单聊聊k8s,和docker之间的关系

前言 随着云原生和微服务架构的快速发展&#xff0c;Kubernetes和Docker已经成为了两个重要的技术。但是有小伙伴通常对这两个技术的关系产生疑惑&#xff1a; 既然有了docker&#xff0c;为什么又出来一个k8s&#xff1f; 它俩之间是竞品的关系吗&#xff1f; 傻傻分不清。…

人工智能|推荐系统——基于tensorflow的个性化电影推荐系统实战(有前端)

代码下载&#xff1a; 基于tensorflow的个性化电影推荐系统实战(有前端).zip资源-CSDN文库 项目简介&#xff1a; dl_re_web : Web 项目的文件夹re_sys&#xff1a; Web app model&#xff1a;百度云下载之后&#xff0c;把model放到该文件夹下recommend&#xff1a; 网络模型相…

Code Composer Studio (CCS) - 文件比较

Code Composer Studio [CCS] - 文件比较 References 鼠标单击选中一个文件&#xff0c;再同时按住 Ctrl 鼠标左键来选中第二个文件&#xff0c;在其中一个文件上鼠标右击选择 Compare With -> Each Other. References [1] Yongqiang Cheng, https://yongqiang.blog.csdn.n…

云计算基础-大页内存

大页内存功能概述 什么是大页内存 简单来说&#xff0c;就是通过增大操作系统页的大小来减小页表&#xff0c;从而避免快表缺失 主要应用场景 主要运用于内存密集型业务的虚拟机&#xff0c;比如对于运行数据库系统的虚拟机&#xff0c;采用HugePages(大页)后&#xff0c;可…

Apache Httpd 常见漏洞解析(全)

一、Apache HTTPD 换行解析漏洞 漏洞编号&#xff1a;CVE-2017-15715 Apache HTTPD是一款HTTP服务器&#xff0c;它可以通过mod_php来运行PHP网页。 其2.4.0~2.4.29版本中存在一个解析漏洞。 在解析PHP时&#xff0c;1.php\x0A将被按照PHP后缀进行解析&#xff0c;导致绕过…

【JS逆向+Python模拟API请求】逆向某一个略微中等的混淆网站,并模拟调用api请求 仅供学习。注:不是源代码混淆,而是一个做代码混淆业务的网站,

逆向日期&#xff1a;2024.02.16 使用工具&#xff1a;Node.js 加密方法&#xff1a;RSA标准库 文章全程已做去敏处理&#xff01;&#xff01;&#xff01; 【需要做的可联系我】 AES解密处理&#xff08;直接解密即可&#xff09;&#xff08;crypto-js.js 标准算法&#xf…

typescript环境搭建,及tsc命令优化

typescript typescript. 是一种由微软开发的 开源 、跨平台的编程语言。. 它是 JavaScript 的超集&#xff0c;最终会被编译为JavaScript代码。. TypeScript添加了可选的静态类型系统、很多尚未正式发布的ECMAScript新特性&#xff08;如装饰器 [1] &#xff09;。. 2012年10月…

六、Datax通过json字符串运行

Datax通过json字符串运行 一、场景二、代码实现 一、场景 制作一个web应用&#xff0c;在页面上配置一个json字符串&#xff0c;保存在数据库里面。在执行json的时候&#xff0c;动态在本地创建一个json文件后执行&#xff0c;并识别是否成功&#xff0c;将执行过程保存在数据…

【Webpack】处理字体图标和音视频资源

处理字体图标资源 1. 下载字体图标文件 打开阿里巴巴矢量图标库open in new window选择想要的图标添加到购物车&#xff0c;统一下载到本地 2. 添加字体图标资源 src/fonts/iconfont.ttf src/fonts/iconfont.woff src/fonts/iconfont.woff2 src/css/iconfont.css 注意字体…

【教程】C++语言基础学习笔记(八)——函数

写在前面&#xff1a; 如果文章对你有帮助&#xff0c;记得点赞关注加收藏一波&#xff0c;利于以后需要的时候复习&#xff0c;多谢支持&#xff01; 【C语言基础学习】系列文章 第一章 《项目与程序结构》 第二章 《数据类型》 第三章 《运算符》 第四章 《流程控制》 第五章…

电商小程序09活动管理

目录 1 创建数据源2 详情页面搭建3 首页轮播图搭建4 最终的效果5 总结 商家在日常运营中经常需要通过活动来进行推广和促销&#xff0c;我们在小程序中也需要考虑这部分的业务。本节我们讲解一下微搭低代码中如何实现活动的功能。 1 创建数据源 展示信息需要将信息存储到数据源…

【Linux系统化学习】文件重定向

目录 文件内核对象 文件描述符的分配规则 重定向 重定向的概念 dup2系统调用 输出重定向 追加重定向 输入重定向 stderr解析 重定向到同一个文件中 分离常规输出和错输出 文件内核对象 上篇文章中我们介绍到了操作系统中的文件&#xff0c;操作系统为了方…

代码随想录算法训练营第31天|● 理论基础 ● 455.分发饼干 ● 376. 摆动序列 ● 53. 最大子序和

文章目录 理论基础分发饼干思路&#xff1a;代码&#xff1a; 摆动序列思路一 贪心算法&#xff1a;代码&#xff1a; 思路二&#xff1a;动态规划&#xff08;想不清楚&#xff09;代码&#xff1a; 最大子序和思路&#xff1a;代码&#xff1a; 理论基础 贪心算法其实就是没…

开关电源电路主要元器件基础知识详解

在学习电子电路过程中&#xff0c;电源我们无法绕开的一个重要部分&#xff0c;很多时候&#xff0c;故障就出现在电源部分&#xff0c;特别是开关电源。开关电源电路主要是由熔断器、热敏电阻器、互感滤波器、桥式整流电路、滤波电容器、开关振荡集成电路、开关变压器、光耦合…

Slider滑动输入条(antd-design组件库)简单使用

1.Slider滑动输入条 滑动型输入器&#xff0c;展示当前值和可选范围。 2.何时使用 当用户需要在数值区间/自定义区间内进行选择时&#xff0c;可为连续或离散值。 组件代码来自&#xff1a; 滑动输入条 Slider - Ant Design 3.本地验证前的准备 参考文章【react项目antd组件-de…

linux系统下vscode portable版本的c++/Cmake环境搭建002:使用 VSIX 安装VSCODE插件(暂记)

使用 VSIX 安装VSCODE插件 在 Visual Studio Code (VSCode) 中&#xff0c;你可以通过以下步骤离线安装插件&#xff1a; 获取插件的 VSIX 文件&#xff1a; 在一个联网环境中&#xff0c;访问 Visual Studio Code Marketplace&#xff0c;搜索并找到你想要的插件。 比如&am…