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

二叉树的非递归遍历|前中后序遍历

二叉树的非递归遍历

文章目录

    • 二叉树的非递归遍历
      • 前序遍历-栈
      • 层序遍历-队列
      • 中序遍历-栈
      • 后序遍历-栈

前序遍历-栈

首先我们应该创建一个Stack 用来存放节点,首先我们想要打印根节点的数据,此时Stack里面的内容为空,所以我们优先将头结点加入Stack。之后我们应该先打印左子树,然后右子树,所以先加入Stack的就是右子树,然后左子树。

public List<Integer> preorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();if (root == null) {return res;}Stack<TreeNode> stack = new Stack<>();//1.根节点入栈stack.push(root);//2.栈不为空while (!stack.isEmpty()) {//2.1出栈,需暂时保存出栈元素TreeNode tmp = stack.pop();res.add(tmp.val);//2.2左右子树不为空的情况下,出栈元素的右子树入栈,左子树入栈if (tmp.right != null) {stack.push(tmp.right);}if (tmp.left != null) {stack.push(tmp.left);}}return res;
}

层序遍历-队列

首先我们应该创建一个Queue用来存放节点,首先我们想要打印根节点的数据,此时Queue里面的内容为空,所以我们优先将头结点加入Queue。之后我们应该先打印左子树,然后右子树,所以先加入Queue的就是左子树,然后右子树。

public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> res = new ArrayList<>();if (root == null) {return res;}Queue<TreeNode> queue = new LinkedList<>();//1.根节点入队列queue.offer(root);//2.队列不为空while (!queue.isEmpty()) {//2.1获取当前队列的元素List<Integer> level = new ArrayList<>();int size = queue.size();for (int i = 0; i < size; i++) {//2.1.1出队列,需暂时保存出队元素TreeNode tmp = queue.poll();level.add(tmp.val);//2.1.2左右子树不为空的情况下,出队元素的左子树入队,右子树入队if (tmp.left != null) {queue.offer(tmp.left);}if (tmp.right != null) {queue.offer(tmp.right);}}//2.2当前队列元素加入到res中res.add(level);}return res;
}

中序遍历-栈

同理创建一个 Stack。

尽可能的将这个节点的左子树压入 Stack,此时栈顶的元素是最左侧的元素,其目的是找到一个最小单位的子树(也就是最左侧的一个节点),并且在寻找的过程中记录了来源,才能返回上层,同时在返回上层的时候已经处理完毕左子树了。

当处理完最小单位的子树时,返回到上层处理了中间节点。(如果把整个左中右的遍历都理解成子树的话,就是处理完 左子树->中间(就是一个节点)->右子树)

如果有右节点,其也要进行中序遍历。

public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();if (root == null) {return res;}Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;while (true) {//1.cur从根节点出发,一直向左保存左子树,直到cur=nullwhile (cur != null) {stack.push(cur);cur = cur.left;}//2.若栈为空,退出循环if (stack.isEmpty()) {break;}//3.出栈TreeNode tmp = stack.pop();res.add(tmp.val);//4.cur指向出栈元素的右子树,//若为空则继续出栈,若不为空再继续向左保存子树cur = tmp.right;}return res;
}

后序遍历-栈

同理创建一个 Stack。

尽可能的将这个节点的左子树压入 Stack,此时栈顶的元素是最左侧的元素

该元素无右子树,或者右子树已经访问过,则可以处理该元素,并用prev记录当前已处理的元素

否则访问右子树,进行后序遍历

    public List<Integer> postorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();if (root == null) {return res;}Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;TreeNode prev = null;while (true) {//1.cur从根节点出发一直向左保存左子树,直到cur=nullwhile (cur != null) {stack.push(cur);cur = cur.left;}//2.若栈为空,退出循环if (stack.isEmpty()) {break;}//3.得到栈顶元素,先不访问(满足条件才可以访问)TreeNode tmp = stack.peek();//4.若栈顶元素无右子树或者右子树已被访问,则可以访问//若prev==tmp.right,则tmp一定是其右子树的根节点。因为此时右子树已访问完毕if (tmp.right == null || tmp.right == prev) {stack.pop();res.add(tmp.val);prev = tmp;} else { //5.cur指向栈顶元素的右子树cur = tmp.right;}}return res;}

相关文章:

二叉树的非递归遍历|前中后序遍历

二叉树的非递归遍历 文章目录 二叉树的非递归遍历前序遍历-栈层序遍历-队列中序遍历-栈后序遍历-栈 前序遍历-栈 首先我们应该创建一个Stack 用来存放节点&#xff0c;首先我们想要打印根节点的数据&#xff0c;此时Stack里面的内容为空&#xff0c;所以我们优先将头结点加入S…...

开源minio-AWS-S3存储的部署及go操作详细

介绍 MinIO是一个开源的分布式对象存储服务&#xff0c;它允许用户在私有云或公有云环境中构建自己的对象存储基础设施。MinIO旨在提供高性能、高可用性的对象存储&#xff0c;并且与Amazon S3兼容&#xff0c;这意味着可以使用S3客户端工具和库直接与MinIO交互&#xff0c;而…...

【Web2D/3D】Canvas(第三篇)

1. 前言 <canvas>是HTML5新增元素&#xff0c;它是一个画板&#xff0c;开发人员基于它的2D上下文或webgl上下文&#xff0c;使用JS脚本绘制简单的动画、可交互画面&#xff0c;甚至进行视频渲染。 本篇介绍基于canvas的2D上下文绘制2D画面的一些方法和属性。 2. canvas…...

紫光展锐T820与飞桨完成I级兼容性测试 助推端侧AI融合创新

近日&#xff0c;紫光展锐高性能5G SoC T820与百度飞桨完成I级兼容性测试&#xff08;基于Paddle Lite工具&#xff09;。测试结果显示&#xff0c;双方兼容性表现良好&#xff0c;整体运行稳定。这是紫光展锐加入百度“硬件生态共创计划”后的阶段性成果。 本次I级兼容性测试完…...

3DV 2024 Oral | SlimmeRF:可动态压缩辐射场,实现模型大小和建模精度的灵活权衡

目前大多数NeRF模型要么通过使用大型模型来实现高精度&#xff0c;要么通过牺牲精度来节省内存资源。这使得任何单一模型的适用范围受到局限&#xff0c;因为高精度模型可能无法适应低内存设备&#xff0c;而内存高效模型可能无法满足高质量要求。为此&#xff0c;本文研究者提…...

【unity学习笔记】4.场景切换

创建空物体→创建脚本挂载在空物体上→打开脚本 1.创建所需要的场景 assets中点击创建场景 2.文件→生成设置 3.将需要的场景拖入 4.场景跳转 创建空对象&#xff0c;将脚本放在空对象上。 注意两个类&#xff1a;场景类、场景管理类 void Start(){//场景跳转SceneManager.Lo…...

LeetCode75| 滑动窗口

目录 643 子数组最大平均数 | 1456 定长子串中元音的最大数目 1004 最大连续1的个数 ||| 1493 删掉一个元素以后全为1的最长子数组 643 子数组最大平均数 | class Solution { public:double findMaxAverage(vector<int>& nums, int k) {double sum 0;double re…...

gulimall-002 分布式基础概念

1、微服务概念 微服务是一种非常流行的架构风格。 拒绝大型单体应用&#xff0c;基于业务边界进行服务微化拆分&#xff0c;各个服务独立部署运行。 每个服务运行在自己的单个进程使用轻量级机制通信可以使用不同的编程语言编写以及不同的数据存储技术 2、集群&分布式&…...

K8s之声明式APIs

大家好&#xff0c;我是升仔 引言 Kubernetes&#xff08;K8s&#xff09;是一个开源的容器编排系统&#xff0c;用于自动化部署、扩展和管理容器化应用。在K8s中&#xff0c;声明式APIs&#xff08;Application Programming Interfaces&#xff09;是一种核心概念&#xff0…...

Hive执行计划

Hive提供了explain命令来展示一个查询的执行计划&#xff0c;这个执行计划对于我们了解底层原理&#xff0c;Hive 调优&#xff0c;排查数据倾斜等很有帮助。 使用语法如下&#xff1a; explain query;在 hive cli 中输入以下命令(hive 2.3.7)&#xff1a; explain select s…...

Leetcode—62.不同路径【中等】

2023每日刷题&#xff08;七十二&#xff09; Leetcode—62.不同路径 超时dfs代码 class Solution { public:int uniquePaths(int m, int n) {int starti 1, startj 1;int ans 0;function<void(int, int)> dfs [&](int i, int j) {if(i m && j n) {a…...

【汇编笔记】初识汇编-内存读写

汇编语言的由来&#xff1a; CPU是计算机的核心&#xff0c;由于计算机只认识二进制&#xff0c;所以CPU执行的指令是二进制。 我们要想让CPU工作&#xff0c;就得给他提供它认识的指令&#xff0c;这一系列的指令的集合&#xff0c;称之为指令集。 指令集&#xff1a; 不同的体…...

Shell脚本通过渗透测试检测服务器安全!

以下是一个简单的 Shell 脚本通过渗透测试来发现服务器漏洞的例子&#xff1a; #!/bin/bash # 设置变量 server_url"http://example.com" server_port"80" script_path"/path/to/script.脚本" # 创建并打开 Web 服务器 web_server$(curl -s $se…...

数据结构--查找

目录 1. 查找的基本概念 2. 线性表的查找 3. 树表的查找 3.1 二叉排序树 3.1.1 定义: 3.1.2 存储结构&#xff1a; 3.1.3 二叉排序树的查找 3.1.4 二叉排序树的插入 3.1.5 二叉排序树删除 3.2 平衡二叉树&#xff08;AVL 3.2.1 为什么要有平衡二叉树 3.2.2 定义 3.3 B-树 3.3.1…...

IntelliJ IDEA Apache Dubbo,IDEA 官方插件正式发布!

作者&#xff1a;刘军 最受欢迎的 Java 集成开发环境 IntelliJ IDEA 与开源微服务框架 Apache Dubbo 社区强强合作&#xff0c;给广大微服务开发者带来了福音。与 IntelliJ IDEA 2023.2 版本一起&#xff0c;Jetbrains 官方发布了一款全新插件 - Apache Dubbo in Spring Frame…...

使用Visual Studio 2022 winform项目打包成安装程序.exe

winform项目打包 1.安装扩展插件 Microsoft Visual Studio Installer Projects 20222.在解决方案上新建一个setup project 项目3.新建成功如下图&#xff0c;之后添加你的winform程序生成之后的debug下的文件4.在Application Folder上点击右键->Add->项目输出->主输出…...

报错-idea pom.xml 有一条灰色横线

1. 背景 打开 idea 更新代码&#xff0c;发现有个 module 的 pom.xml 有一条灰色横线&#xff0c;导致这个 module 没有加载成功。 2. 原因 1&#xff09; 可能本地 Remove 了这个 module 2&#xff09;本地删除了这个 module &#xff0c;又从远端拉取了回来 3&#xff09…...

openmediavault(OMV) (19)云相册(3)mt-photos

简介 MT Photos是一款为Nas用户量身打造的照片管理系统。通过AI技术,自动将您的照片整理、分类,包括但不限于时间、地点、人物、照片类型。可以在任何支持Docker的系统中运行它。详情可查看mtmt.tech官网,mt-photos是付费订阅使用的,也可以一次性付费永久使用,具体使用mt…...

基于openGauss5.0.0全密态数据库等值查询小案例

基于openGauss5.0.0全密态数据库等值查询小案例 一、全密态数据库简介二、环境说明三、测试步骤四、使用约束 一、全密态数据库简介 价值体现&#xff1a; 密态数据库意在解决数据全生命周期的隐私保护问题&#xff0c;使得系统无论在何种业务场景和环境下&#xff0c;数据在传…...

Oracle中varchar2和nvarchar2的区别

Oracle中的varchar2和nvarchar2都是可变长度的字符数据类型&#xff0c;这意味着它们能够根据实际存储的数据长度来动态调整占用的空间。但它们之间有以下主要区别&#xff1a; 1. 字符编码和存储&#xff1a; - VARCHAR2&#xff1a;存储的是字节字符串&#xff0c;对字符…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

06 Deep learning神经网络编程基础 激活函数 --吴恩达

深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

短视频矩阵系统文案创作功能开发实践,定制化开发

在短视频行业迅猛发展的当下&#xff0c;企业和个人创作者为了扩大影响力、提升传播效果&#xff0c;纷纷采用短视频矩阵运营策略&#xff0c;同时管理多个平台、多个账号的内容发布。然而&#xff0c;频繁的文案创作需求让运营者疲于应对&#xff0c;如何高效产出高质量文案成…...

莫兰迪高级灰总结计划简约商务通用PPT模版

莫兰迪高级灰总结计划简约商务通用PPT模版&#xff0c;莫兰迪调色板清新简约工作汇报PPT模版&#xff0c;莫兰迪时尚风极简设计PPT模版&#xff0c;大学生毕业论文答辩PPT模版&#xff0c;莫兰迪配色总结计划简约商务通用PPT模版&#xff0c;莫兰迪商务汇报PPT模版&#xff0c;…...

C++ 设计模式 《小明的奶茶加料风波》

&#x1f468;‍&#x1f393; 模式名称&#xff1a;装饰器模式&#xff08;Decorator Pattern&#xff09; &#x1f466; 小明最近上线了校园奶茶配送功能&#xff0c;业务火爆&#xff0c;大家都在加料&#xff1a; 有的同学要加波霸 &#x1f7e4;&#xff0c;有的要加椰果…...

Oracle11g安装包

Oracle 11g安装包 适用于windows系统&#xff0c;64位 下载路径 oracle 11g 安装包...