【遍历】非递归法 二叉树的前中后序遍历
文章目录
- 非递归法
- 前序遍历
- 后序遍历
- 中序遍历
- 递归法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失效&…...
【杂谈】-递归进化:人工智能的自我改进与监管挑战
递归进化:人工智能的自我改进与监管挑战 文章目录 递归进化:人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管?3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...
Linux链表操作全解析
Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表?1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...
椭圆曲线密码学(ECC)
一、ECC算法概述 椭圆曲线密码学(Elliptic Curve Cryptography)是基于椭圆曲线数学理论的公钥密码系统,由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA,ECC在相同安全强度下密钥更短(256位ECC ≈ 3072位RSA…...
(十)学生端搭建
本次旨在将之前的已完成的部分功能进行拼装到学生端,同时完善学生端的构建。本次工作主要包括: 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...
MVC 数据库
MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...
高等数学(下)题型笔记(八)空间解析几何与向量代数
目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...
linux 下常用变更-8
1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行,YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID: YW3…...
Fabric V2.5 通用溯源系统——增加图片上传与下载功能
fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...
日常一水C
多态 言简意赅:就是一个对象面对同一事件时做出的不同反应 而之前的继承中说过,当子类和父类的函数名相同时,会隐藏父类的同名函数转而调用子类的同名函数,如果要调用父类的同名函数,那么就需要对父类进行引用&#…...
