【遍历】非递归法 二叉树的前中后序遍历
文章目录
- 非递归法
- 前序遍历
- 后序遍历
- 中序遍历
- 递归法DFS
非递归法
通过栈Stack来模拟递归。
前序遍历
LeetCode 144

前序遍历:1 2 3
定义:存放答案的List、栈Stack
- 将root入栈
- 出栈:node,为null则舍弃
- 将node放入list
- 将node.right入栈
- 将node.left入栈
- 栈不为空则重复2-5步
为了让左节点优先于右节点出栈,因此先将右节点入栈。
class Solution {public List<Integer> preorderTraversal(TreeNode root) {Stack<TreeNode> stack = new Stack<>();List<Integer> list = new LinkedList<>();stack.push(root);while(!stack.empty()){TreeNode node = stack.pop();if(node==null)continue;list.add(node.val);stack.push(node.right);stack.push(node.left);}return list;}
}
后序遍历
LeetCode 145

后序遍历:2 3 1
后序遍历仅需在前序遍历的代码中修改3处即可。
由前序遍历1 2 3 改为 1 3 2 再翻转为 2 3 1即为答案。
class Solution {public List<Integer> postorderTraversal(TreeNode root) {Stack<TreeNode> stack = new Stack<>();List<Integer> list = new LinkedList<>();stack.push(root);while(!stack.empty()){TreeNode node = stack.pop();if(node == null)continue;list.add(node.val);stack.push(node.left); // 先放入左节点stack.push(node.right); }Collections.reverse(list); // 反转return list;}
}
中序遍历
LeetCode 94
中序遍历代码与前序和后续不同。

中序遍历: 4 2 5 1 3。
思考:要想先输出4,则需要将左节点持续入栈,直到为null,此时出栈即为4,然后将其右节点入栈…
同样的,定义存放结果的list和栈stack。
- cur = root
- cur不为空或者栈不为空
- 循环 将cur入栈,并将cur赋值其左节点,直到为空
- 出站node,将node加入list
- 将node赋值为node.left
- 重复2 - 5步
class Solution {public List<Integer> inorderTraversal(TreeNode root) {Stack<TreeNode> stack = new Stack<>();List<Integer> list = new LinkedList<>();TreeNode cur = root;while(cur!=null||!stack.empty()){while(cur!=null){stack.push(cur);cur = cur.left;}TreeNode node = stack.pop(); list.add(node.val);cur = node.right;}return list;}
}
递归法DFS
class Solution {List<Integer> list1 = new LinkedList<>(); // 前序List<Integer> list2 = new LinkedList<>(); // 中序List<Integer> list3 = new LinkedList<>(); // 后序public List<Integer> inorderTraversal(TreeNode root) {traverse(root);return list2; }void traverse(TreeNode root){if(root==null)return;list1.add(root.val); traverse(root.left); // 递归左节点list2.add(root.val);traverse(root.right); // 递归右节点list3.add(root.val);}}
参考:
- cyc2018
- 代码随想录 B站
相关文章:
【遍历】非递归法 二叉树的前中后序遍历
文章目录 非递归法前序遍历后序遍历中序遍历 递归法DFS 非递归法 通过栈Stack来模拟递归。 前序遍历 LeetCode 144 前序遍历:1 2 3 定义:存放答案的List、栈Stack 将root入栈出栈:node,为null则舍弃将node放入list将node.r…...
Python将tiff转换成png
文章目录 问题描述解决方案压缩并转换参考文献 问题描述 base64 的 image/tiff 无法在页面直接展示,将其转换为 image/png 解决方案 from io import BytesIOfrom PIL import Imagewith Image.open(a.tiff) as image:bytesIO BytesIO()image.save(bytesIO, format…...
【大数据】-- 部署 Flink kubernetes operator
目录 1.说明 1.1 版本 1.2 kubernetes 环境 1.3 参考 2.安装步骤 2.1 安装本地 kubernetes 环境...
能够完成两个数的算术运算的单地址指令,地址码指明一个操作数,另一个操作数来自( )方式
【计算机组成原理错题】能够完成两个数的算术运算的单地址指令,地址码指明一个操作数,另一个操作数来自( )方式。 A.立即寻址 B.隐含寻址 C.间接寻址 D.基址寻址 正确答案:B 因为另一个操作数来自于累加器ACC,而这种方式属于隐含寻址。 在指令…...
数据库数据恢复-Oracle数据库数据恢复案例
数据库数据恢复环境: Oracle数据库ASM磁盘组有4块成员盘。 数据库故障&分析: Oracle数据库ASM磁盘组掉线 ,ASM实例无法挂载,用户联系我们要求恢复oracle数据库。 数据库数据恢复工程师拿到磁盘后,先将所有磁盘以只…...
对于msvcr120.dll丢失的问题,分享几种解决方法
msvcr120.dll的作用是提供一系列的运行时函数和功能,以便应用程序能够正常运行。这些函数和功能包括内存管理、异常处理、输入输出操作、数学运算等。在没有这个库文件的情况下,应用程序可能无法正常启动或执行特定的功能,甚至会出现错误提示…...
网络安全进阶学习第十三课——SQL注入Bypass姿势
文章目录 一、等号被过滤二、substr、mid等被过滤三、逗号被过滤四、and/or被过滤五、空格被过滤五、其他绕过方式 一、等号被过滤 1、like,rlike语句,其中rlike是正则2、大于号>,小于号<3、符号<>:<>为不等于…...
vue3 provide inject实现强制刷新
1、在 App.vue 文件里写入 provide 的方法 <template> <div id"app"><keep-alive> <router-view v-if"isRouterAlive"></router-view></keep-alive> </div> </template> <script> export default …...
Neo4j笔记-数据迁移(导出/导入)
这里先说明以下几点: Neo4j在4.0下版本默认的库名是:graph.db Neo4j在4.0上版本默认的库名是:neo4j.db 不管是Neo4j,还是Neo4j Desktop,都会在bin目录下有neo4j、neo4j-admin软件。在conf目录下,有neo4j.…...
请求转发和请求重定向
目录 1. 定义层面 2. 请求方层面 3. 数据共享层面 4. 最终 url 层面 5. 代码实现层面 请求转发 请求重定向 在Java中,跳转网页的方式有两种,一种是请求转发,另一种是请求重定向,而实际上,这两种方式是有着明显…...
TOMCAT的多实例部署和动静分离
tomcat的多实例 动静分离 排错小工具: telnet工具:yum -y install telnet telnet工具用于测试端口是否正常 telnet 20.0.0.101 80Tomcat多实例部署: 一台服务器上有多个tomcat的服务 1.安装好 jdk 2.安装 tomcat cd /opt tar zxvf apache-…...
阿里微服务seata组件tc告诉rm进行提交的时候,rm提交失败了seata怎么办呢?
当Seata的TC(Transaction Coordinator)向RM(Resource Manager)发起提交请求时,如果RM提交失败,Seata会采取以下步骤处理: 重试机制:Seata会尝试多次向RM发送提交请求,以确…...
已解决 RuntimeError: There is no current event loop in thread ‘Thread-1‘.
作者主页:爱笑的男孩。的博客_CSDN博客-深度学习,活动,python领域博主爱笑的男孩。擅长深度学习,活动,python,等方面的知识,爱笑的男孩。关注算法,python,计算机视觉,图像处理,深度学习,pytorch,神经网络,opencv领域.https://blog.csdn.net/Code_and516?typeblog个…...
Android的学习系列之Android Studio Setup安装
Android的学习系列之Android Studio Setup安装 [TOC](Android的学习系列之Android Studio Setup安装) 前言Android平台搭建总结 前言 还是项目需要,暂时搭建安卓的运行平台。 Android平台搭建 安装包 双击安装包,进入安装。 下一步 根据自己需求&a…...
Python测试框架pytest:常用参数、查找子集、参数化、跳过
Pytest是一个基于python的测试框架,用于编写和执行测试代码。pytest主要用于API测试,可以编写代码来测试API、数据库、UI等。 pytest是一个非常成熟的全功能的Python测试框架,主要有以下几个优点: 简单灵活,容易上手。…...
Android 13 Hotseat定制化修改
一.背景 由于需求是需要自定义修改Hotseat,所以此篇文章是记录如何自定义修改hotseat的,应该可以覆盖大部分场景,修改点有修改hotseat布局方向,hotseat图标数量,hotseat图标大小,hotseat布局位置,hotseat图标禁止形成文件夹,hotseat图标禁止移动到Launcher中,下面开始…...
【VUE】7、VUE项目中集成watermark实现页面添加水印
在网站浏览中,常常需要网页水印,以便防止用户截图或录屏暴露敏感信息后,方便追踪用户来源。 1、安装 watermark 在 package.json 文件 dependencies 节点增加 watermark-dom 依赖 "watermark-dom": "2.3.0"然后执行命…...
Rider无法识别Todo Comment
最近因为vs code很难识别到代码中的usage和definition,改用Rider了。 但是一开始就哪里有点不对, 比如我主题的颜色总是有些地方无法识别出来。比如我每次从Unity中点击脚本文件,都只能识别到某一个特定的文件夹,而不能打开整个…...
用 docker 创建 jmeter 容器,能做性能测试?
我们都知道,jmeter 可以做接口测试,也可以用于性能测试,现在企业中性能测试也大多使用 jmeter。docker 是最近这些年流行起来的容器部署工具,可以创建一个容器,然后把项目放到容器中,就可以构建出一个独立的…...
Token 失效退出至登录页面
目录 前端设置: 1. 在登录页面,调用登录的接口后,直接获取当前时间并保存在本地,类似保存token。 2. 在路由守卫 获取本机存储的时间戳,加15分钟与当前时间进行对比,如果大于当前时间说明token失效&…...
Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...
Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件
今天呢,博主的学习进度也是步入了Java Mybatis 框架,目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学,希望能对大家有所帮助,也特别欢迎大家指点不足之处,小生很乐意接受正确的建议&…...
C# 类和继承(抽象类)
抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...
听写流程自动化实践,轻量级教育辅助
随着智能教育工具的发展,越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式,也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建,…...
服务器--宝塔命令
一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行! sudo su - 1. CentOS 系统: yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...
LeetCode - 199. 二叉树的右视图
题目 199. 二叉树的右视图 - 力扣(LeetCode) 思路 右视图是指从树的右侧看,对于每一层,只能看到该层最右边的节点。实现思路是: 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...
springboot整合VUE之在线教育管理系统简介
可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生,小白用户,想学习知识的 有点基础,想要通过项…...
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...
【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看
文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...
Git常用命令完全指南:从入门到精通
Git常用命令完全指南:从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...
