【遍历】非递归法 二叉树的前中后序遍历
文章目录
- 非递归法
- 前序遍历
- 后序遍历
- 中序遍历
- 递归法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失效&…...
Universal-x86-Tuning-Utility:解锁硬件潜能,让你的电脑发挥100%性能!
Universal-x86-Tuning-Utility:解锁硬件潜能,让你的电脑发挥100%性能! 【免费下载链接】Universal-x86-Tuning-Utility Unlock the full potential of your Intel/AMD based device. 项目地址: https://gitcode.com/gh_mirrors/un/Universa…...
从零构建私有化AI助手:基于LLM框架的RAG与工具调用实战
1. 项目概述:从“墨灵”到个人AI助手的进化之路最近在GitHub上看到一个挺有意思的项目,叫“gojue/moling”。光看这个名字,你可能会有点摸不着头脑——“墨灵”?听起来像是个游戏角色或者某种神秘力量。但如果你点进去,…...
BlockTheSpot终极指南:3步免费解锁Spotify高级功能,彻底告别广告干扰 [特殊字符]
BlockTheSpot终极指南:3步免费解锁Spotify高级功能,彻底告别广告干扰 🎵 【免费下载链接】BlockTheSpot Video, audio & banner adblock/skip for Spotify 项目地址: https://gitcode.com/gh_mirrors/bl/BlockTheSpot 还在为Spoti…...
抖音直播保存终极指南:douyin-downloader完整解决方案
抖音直播保存终极指南:douyin-downloader完整解决方案 【免费下载链接】douyin-downloader A practical Douyin downloader for both single-item and profile batch downloads, with progress display, retries, SQLite deduplication, and browser fallback suppo…...
深度学习模型集成:堆叠泛化实战指南
1. 深度学习模型集成方法概述在机器学习实践中,单个模型的表现往往存在局限性。模型集成技术通过组合多个模型的预测结果,通常能够获得比单一模型更优的性能。其中,堆叠泛化(Stacking Generalization)是一种强大的集成…...
茉莉花插件:3步解决Zotero中文文献管理的世纪难题
茉莉花插件:3步解决Zotero中文文献管理的世纪难题 【免费下载链接】jasminum A Zotero add-on to retrive CNKI meta data. 一个简单的Zotero 插件,用于识别中文元数据 项目地址: https://gitcode.com/gh_mirrors/ja/jasminum 如果你是一名中文科…...
LoongFlow:专为龙芯架构深度优化的国产工作流引擎设计与实践
1. 项目概述:LoongFlow,一个为龙芯生态量身打造的流程引擎最近在梳理一些国产化替代项目的基础设施选型时,我反复被一个名字吸引:LoongFlow。乍一看,这像是一个普通的开源工作流引擎,但它的前缀“baidu-bai…...
OpenPose与Stable Diffusion协同生成姿态控制图像
1. 项目概述:OpenPose与Stable Diffusion的协同工作流去年在开发一个动画项目时,我需要批量生成风格统一但姿态各异的人物图像。传统手动调整不仅效率低下,而且难以保持角色比例的一致性。这时OpenPose与Stable Diffusion的组合方案完美解决了…...
终极指南:5分钟学会用KMS_VL_ALL_AIO一键永久激活Windows和Office
终极指南:5分钟学会用KMS_VL_ALL_AIO一键永久激活Windows和Office 【免费下载链接】KMS_VL_ALL_AIO Smart Activation Script 项目地址: https://gitcode.com/gh_mirrors/km/KMS_VL_ALL_AIO 还在为Windows系统激活弹窗烦恼吗?Office软件突然变成只…...
Kubernetes 垃圾收集(Garbage Collection)完全指南:对象生命周期管理
Kubernetes 垃圾收集(Garbage Collection)完全指南:对象生命周期管理 1. Owner 和 Dependent(所有者与依赖对象) 1.1 核心概念Owner(所有者):Kubernetes 中部分对象可作为其他对象的…...
