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

力扣刷题 二叉树的迭代遍历

题干

给你二叉树的根节点 root ,返回它节点值的 前序 遍历。

示例 1:

输入:root = [1,null,2,3]
输出:[1,2,3]

示例 2:

输入:root = []
输出:[]

示例 3:

输入:root = [1]
输出:[1]

示例 4:

输入:root = [1,2]
输出:[1,2]

示例 5:

输入:root = [1,null,2]
输出:[1,2]

解题思路

我们上次使用了递归来完成前中后序遍历,这次我们用迭代法来实现。

前序遍历

大体思路是用栈来实现遍历。我们先建立一个栈,把根节点root压入栈。

我们模拟从根节点root开始,先设置一个循环,当栈不为空的时候,对每一个栈顶元素循环操作。因此根节点只是一个个例,后面在写代码的时候不能只考虑根节点的情形。

我们先把root从栈中弹出,如果它不为空,则将其放入结果数组中。如果为空的话,就跳出本次循环,对下一个栈元素进行操作。(根节点是第一个栈元素,自然不会有下一个栈元素,但是我们写代码考虑的是全局情况)

然后依次把它的右子树和左子树压入栈中,因为栈是后进先出的,所以下一个出栈的就是左子树,符合中左右的顺序。

//迭代法
class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {//建立一个栈stack<TreeNode*> st;//建立一个数组保存遍历结果vector<int> result;//将根节点入栈st.push(root); // 在栈不为空的情况下,重复以下操作while(!st.empty()){//将栈顶元素弹出TreeNode* node = st.top();st.pop();//当根节点不为空if(node != NULL){// 将栈顶元素放入结果数组result.push_back(node->val);}//若为空, 则忽略这个节点,去访问下一个节点else{continue;}//将节点的右子树的根节点放入栈st.push(node->right);//将节点的左子树的根节点放入栈,这样下一个遍历的就是左子树st.push(node->left); }// 返回遍历的结果return result;}
};

写完了前序遍历的迭代法遍历,后序遍历就可以轻松写出了,因为前序遍历的顺序是中左右,而后序遍历是左右中。想要从前序变为后序,只需先将左右调换位置,变成中右左,再翻转数组就实现左右中了。而左右调换位置和简单,只需将入栈的顺序调换即可。而翻转函数之前我们也接触过。

后序遍历代码如下

这里我稍微修改了写法,把根节点root和普通根节点的情况做了区分,可能更容易理解,但本质相同。

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

而中序遍历就没有那么简单了。

为了解释清楚,我说明一下 刚刚在迭代的过程中,其实我们有两个操作:

  1. 处理:将元素放进result数组中
  2. 访问:遍历节点

分析一下为什么刚刚写的前序遍历的代码,不能和中序遍历通用呢,因为前序遍历的顺序是中左右,先访问的元素是中间节点,要处理的元素也是中间节点,所以刚刚才能写出相对简洁的代码,因为要访问的元素和要处理的元素顺序是一致的,都是中间节点。

那么再看看中序遍历,中序遍历是左中右,先访问的是二叉树顶部的节点,然后一层一层向下访问,直到到达树左面的最底部,再开始处理节点(也就是在把节点的数值放进result数组中),这就造成了处理顺序和访问顺序是不一致的。

那么在使用迭代法写中序遍历,就需要借用指针的遍历来帮助访问节点,栈则用来处理节点上的元素。

我们设置cur为指针,指针帮助我们一层层访问左子树,直到叶子节点。而当到叶子节点则意味着我们要在做处理了,把根节点弹出,放入结果数组,再访问根节点的右子树,继续层层访问左子树,直到叶子节点。

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;//用指针来访问元素TreeNode* cur = root;//当栈不为空, 当前根节点不为空时,循环以下操作while( cur != NULL||!st.empty()){// 如果指针不为空if(cur != NULL){st.push(cur);cur = cur->left;}//指针为空,说明要开始处理元素,则弹出栈顶else{//弹出根节点cur = st.top();st.pop();//放入结果数组result.push_back(cur->val);//访问根节点的右子树cur = cur->right;}  }return result;}
};
while(cur !=NULL||!st.empty()){

 这段代码是循环结束的条件,注意当cur指向根节点root,栈那是还是空的,所以要加一个cur不是空的条件。

相关文章:

力扣刷题 二叉树的迭代遍历

题干 给你二叉树的根节点 root &#xff0c;返回它节点值的 前序 遍历。 示例 1&#xff1a; 输入&#xff1a;root [1,null,2,3] 输出&#xff1a;[1,2,3]示例 2&#xff1a; 输入&#xff1a;root [] 输出&#xff1a;[]示例 3&#xff1a; 输入&#xff1a;root [1] 输…...

【二】Django小白三板斧

今日内容 静态文件配置 request对象方法初识 pycharm链接数据库&#xff08;MySQL&#xff09; django链接数据库&#xff08;MySQL&#xff09; Django ORM简介 利用ORM实现数据的增删查改 【一】Django小白三板斧 HttpResponse 返回字符串类型的数据 render 返回HTML文…...

MyBatis的基本应用

源码地址 01.MyBatis环境搭建 添加MyBatis的坐标 <!--mybatis坐标--><dependency><groupId>org.mybatis</groupId><artifactId>mybatis</artifactId><version>3.5.9</version></dependency><!--mysql驱动坐…...

Day80:服务攻防-中间件安全HW2023-WPS分析WeblogicJettyJenkinsCVE

目录 中间件-Jetty-CVE&信息泄漏 CVE-2021-34429(信息泄露) CVE-2021-28169(信息泄露) 中间件-Jenkins-CVE&RCE执行 cve_2017_1000353 CVE-2018-1000861 cve_2019_1003000 中间件-Weblogic-CVE&反序列化&RCE 应用金山WPS-HW2023-RCE&复现&上线…...

使用generator实现async函数

我们先来看一下async函数是怎么使用的 const getData (sec) > new Promise((resolve) > {setTimeout(() > resolve(sec * 2), sec * 1000);})// aim to get this asycnFun by generator async function asyncFun() {const data1 await getData(1);const data2 awa…...

go并发请求url

sync.WaitGroup写法 package mainimport ("database/sql""fmt""net/http""sync""time"_ "github.com/go-sql-driver/mysql" )func main() {//开始计时start : time.Now()//链接数据库&#xff0c;用户名&#xf…...

刷题之Leetcode704题(超级详细)

704. 二分查找 力扣题目链接(opens new window)https://leetcode.cn/problems/binary-search/ 给定一个 n 个元素有序的&#xff08;升序&#xff09;整型数组 nums 和一个目标值 target &#xff0c;写一个函数搜索 nums 中的 target&#xff0c;如果目标值存在返回下标&am…...

leetcode热题100.前k个高频元素

作者&#xff1a;晓宜 &#x1f308;&#x1f308;&#x1f308; 个人简介&#xff1a;互联网大厂Java准入职&#xff0c;阿里云专家博主&#xff0c;csdn后端优质创作者&#xff0c;算法爱好者 ❤️❤️❤️ 你的关注是我前进的动力&#x1f60a; Problem: 347. 前 K 个高频元…...

LangChain Demo | Agent X ReAct X wikipedia 询问《三体》的主要内容

背景 LangChain学习中&#xff0c;尝试改了一下哈里森和吴恩达课程当中的问题&#xff0c;看看gpt-3.5-turbo在集成了ReAct和wikipedia后&#xff0c;如何回答《三体》的主要内容是什么这个问题&#xff0c;当然&#xff0c;主要是为了回答这问题时LangChain内部发生了什么。所…...

Revit 2025新功能一览~

Hello大家好&#xff01;我是九哥~ Revit2025已经更新&#xff0c;安装后&#xff0c;简单试了下&#xff0c;还是挺不错的&#xff0c;流畅度啊&#xff0c;新功能啊&#xff0c;看来还是有听取用户意见的&#xff0c;接下来就简单看看都有哪些新功能。 好了&#xff0c;今天的…...

Head First Design Patterns -代理模式

什么是代理模式 代理模式为另一个对象提供替身或者占位符&#xff0c;以便控制客户对对象的访问&#xff0c;管理访问的方式有很多种。例如远程代理、虚拟代理、保护代理等。 远程代理&#xff1a;管理客户和远程对象之间的交互。 虚拟代理&#xff1a;控制访问实例化开销大的对…...

第十三题:天干地支

题目描述 古代中国使用天干地支来记录当前的年份。 天干一共有十个&#xff0c;分别为&#xff1a;甲&#xff08;jiǎ&#xff09;、乙&#xff08;yǐ&#xff09;、丙&#xff08;bǐng&#xff09;、丁&#xff08;dīng&#xff09;、戊&#xff08;w&#xff09;、己&a…...

8000预算可以购买阿里云服务器配置整理

一个月8000元预算如何选择阿里云服务器配置&#xff1f;八千预算可选的阿里云服务器配置相当高了&#xff0c;这个预算可以购买阿里云企业级独享型云服务器&#xff0c;至少8核以上的配置&#xff0c;这个预算可以支持复杂、高负载或大规模的业务需求。阿里云服务器网整理8000元…...

游戏APP如何提高广告变现收益的同时,保证用户留存率?

APP广告变现对接第三方聚合广告平台主要通过SDK文档对接&#xff0c;一些媒体APP不具备专业运营广告变现的对接能力和资源沉淀&#xff0c;导致APP被封控&#xff0c;设置列入黑名单&#xff0c;借助第三方聚合广告平台进行商业化变现是最佳选择。#APP广告变现# 接入第三方平台…...

Linux ulimit命令教程:如何查看和设置系统资源限制(附实例详解和注意事项)

Linux ulimit命令介绍 ulimit是一个内置的Linux shell命令&#xff0c;它允许查看或限制单个用户可以消耗的系统资源量。在有多个用户和系统性能问题的环境中&#xff0c;限制资源使用是非常有价值的。 Linux ulimit命令适用的Linux版本 ulimit命令在所有主流的Linux发行版中…...

(delphi11最新学习资料) Object Pascal 学习笔记---第8章第5节(封闭类和Final方法)

8.5.2 封闭类和Final方法 如前所述&#xff0c;Java 采用非常动态的方法&#xff0c;默认情况下采用延迟绑定&#xff08;或虚函数&#xff09;。因此&#xff0c;Java 语言引入了一些概念&#xff0c;如不能继承的类&#xff08;封闭类&#xff09;和不能在派生类中覆盖的方法…...

vue3从精通到入门12:vue3的生命周期和组件

生命周期&#xff1a; 生命周期钩子主要包括&#xff1a; beforeCreate&#xff1a;组件实例被创建之前调用。在这个阶段&#xff0c;组件的 props 和 data 还未被初始化。created&#xff1a;组件实例创建完成后调用。在这个阶段&#xff0c;组件的 props 和 data 已经被初始…...

力扣热题100_链表_21_合并两个有序链表

文章目录 题目链接解题思路解题代码 题目链接 21. 合并两个有序链表 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1&#xff1a; 输入&#xff1a;l1 [1,2,4], l2 [1,3,4] 输出&#xff1a;[1,1,2,3,4,4] 示例…...

探索未来智慧酒店网项目接口架构

在数字化时代&#xff0c;智慧酒店已成为酒店业发展的重要趋势之一。智慧酒店网项目接口架构作为支撑智慧酒店运营的核心技术之一&#xff0c;其设计和优化对于提升用户体验、提高管理效率具有重要意义。本文将深入探讨智慧酒店网项目接口架构的设计理念和关键要素。 ### 智慧…...

os模块篇(十三)

文章目录 os.mknod(path, mode0o600, device0, *, dir_fdNone)os.major(device, /)os.minor(device, /)os.makedev(major, minor, /)os.pathconf(path, name)os.readlink(path, *, dir_fdNone)os.remove(path, *, dir_fdNone)os.removedirs(name)os.rename(src, dst, *, src_di…...

【JavaEE初阶系列】——文件操作 IO 之 文件系统操作

目录 &#x1f4dd;认识文件 &#x1f6a9;树型结构组织 和 目录 &#x1f388;绝对路径和相对路径 &#x1f6a9;文件类型 &#x1f4dd;文件系统操作 &#x1f388;File 概述 &#x1f388;File类的使用 1. 绝对路径 vs 相对路径 2. 路径分隔符 3. 静态成员变量 4…...

JAVA 学习·类与方法

不同于 C &#xff0c;Java 是一门面向对象的编程语言。C 也有面向对象的内容&#xff0c;但是 C 和 Java 在方法的具体实现上存在区别。 方法的定义 方法(method)是为执行一个复杂操作组合在一起的语句集合。一个类中可以声明多个方法。其语法是采用 BNF 范式&#xff08;Bac…...

4. python练习题4-水仙花数

4. python练习题4-水仙花数 【目录】 文章目录 4. python练习题4-水仙花数1. 目标任务2. 水仙花数的特点3. 如何判断一个数是否是水仙花数&#xff1f;4. 打印3位水仙花数5. 判断一个数是不是水仙花数6. 列表推导式6. 列表推导式判断一个数是不是水仙花数 【正文】 1. 目标任务…...

【Qt 学习笔记】Qt 开发环境的搭建 | Qt 安装教程

博客主页&#xff1a;Duck Bro 博客主页系列专栏&#xff1a;Qt 专栏关注博主&#xff0c;后期持续更新系列文章如果有错误感谢请大家批评指出&#xff0c;及时修改感谢大家点赞&#x1f44d;收藏⭐评论✍ Qt 开发环境的搭建 | Qt 安装教程 文章编号&#xff1a;Qt 学习笔记 /…...

ids工业相机与电控位移台同步控制及数据采集

通过VS2017和OpenCV,实现ids工业相机与电控位移台同步控制及数据采集 目录项目环境配置代码流程及思路项目架构项目开发运行效果开发关键ids相机配置位移台环境配置相机头文件相机参数设置保存图像函数设置电控位移台头文件电控位移台设置参数最后就是通过main函数进行调用和控…...

景联文科技提供高质量医疗健康AI大模型数据

医疗行业是典型的知识和技术密集型行业&#xff0c;其发展水平直接关系到国民健康和生命质量。 医疗健康AI大模型&#xff0c;作为人工智能的一个分支&#xff0c;能够通过学习大量的数据来生成新的数据实例&#xff0c;在医药研发、医学影像、医疗文本分析等都有广泛的应用前景…...

【Python第三方库】lxml 解析器和xpath路径语言

1.lxml是做什么的 是xml/html的解析器&#xff0c;主要是用来解析和提取html/xml数据 2.lxml语法 使用etree.HTML(html字符串)&#xff0c;将字符串转换为Element对象通过使用Element对象.xpath(语法)提取信息,返回的是一个列表的内存地址&#xff0c;需要通过使用索引获取信…...

Java(Lambda、集合)、题解

一、Lambda表达式 标准格式 &#xff08;&#xff09;对应方法的形参 &#xff1b;->固定格式 注意点&#xff1a; Lambda表达式可以用来简化匿名内部类的书写 Lambda表达式只能简化函数式接口的匿名内部类的写法 函数式接口: 有且仅有一个抽象方法的接口叫做函数式接口&…...

Transformer学习: Transformer小模块学习--位置编码,多头自注意力,掩码矩阵

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 Transformer学习 1 位置编码模块1.1 PE代码1.2 测试PE1.3 原文代码 2 多头自注意力模块2.1 多头自注意力代码2.2 测试多头注意力 3 未来序列掩码矩阵3.1 代码3.2 测试掩码 1 …...

easyexcel 动态列导出

1. 引入easyexcel <dependency><groupId>com.alibaba</groupId><artifactId>easyexcel</artifactId><version>3.2.1</version></dependency> 2.导出write public void export(HttpServletResponse response) {try {String f…...

wordpress主题的css在什么位置/税收大数据

1. 检查sql文件路径是否正确&#xff1b;2. 将sql文件移动到C:/Windows/Temp目录下&#xff0c;再打开试试。 转载于:https://www.cnblogs.com/Youyou-2608/p/8994202.html...

做网站赚多少/微信上如何投放广告

什么是正则表达式正则表达式是一种工具&#xff0c;和其他工具一样&#xff0c;它是人们为了解决特定的问题而发明的&#xff0c;主要有两种用途&#xff1a;一种是查找特定的信息&#xff08;搜索&#xff09;另一种是查找并编辑特定的信息&#xff08;替换&#xff09;它是文…...

佛山正规网站建设报价/搜索引擎排名优化方案

http://examples.adobe.com/flex3/devnet/networkmonitor/main.html 转载于:https://www.cnblogs.com/taoj/archive/2011/03/31/2001288.html...

厦门市建设局网站文件/百度网址大全官方网站

ChatGPT是程序员的好帮手&#xff1f;还是要干掉程序员&#xff1f;我觉得不仅要看它生成代码的能力&#xff0c;更关键的是要看它是否具备强大的设计能力。设计能力有两个层面&#xff0c;一个是高层的&#xff0c;例如架构设计&#xff0c;系统设计。一个是相对低层的设计能力…...

公司做网站可以用个人域名/百度官方网

转过 霓虹闪烁的街头以后 视野中出现一座摩天大楼 广告 牌上两个字晶莹通透 叫做梦想 有心之人才能触碰 伸出 双手 尝试触摸蓝色天空 微风 将头发吹动 握紧 双手 抬起头仰望着天空 看那 阳光洒下来 眼中滑过 追逐着的车流 耳中响过 时间在不停奔走 心中闪过 不安分的念头 那就是…...

班服定制网站/深圳关键词

css文字属性 1.规定文字样式的属性 格式&#xff1a;font-style: normal; 定义字体的风格 <style type"text/css"> p.normal {font-style:normal} p.italic {font-style:italic} p.oblique {font-style:oblique} </style>属性值 normal: 默认的&…...