二叉树的非递归遍历|前中后序遍历
二叉树的非递归遍历
文章目录
- 二叉树的非递归遍历
- 前序遍历-栈
- 层序遍历-队列
- 中序遍历-栈
- 后序遍历-栈
前序遍历-栈
首先我们应该创建一个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 用来存放节点,首先我们想要打印根节点的数据,此时Stack里面的内容为空,所以我们优先将头结点加入S…...
开源minio-AWS-S3存储的部署及go操作详细
介绍 MinIO是一个开源的分布式对象存储服务,它允许用户在私有云或公有云环境中构建自己的对象存储基础设施。MinIO旨在提供高性能、高可用性的对象存储,并且与Amazon S3兼容,这意味着可以使用S3客户端工具和库直接与MinIO交互,而…...
【Web2D/3D】Canvas(第三篇)
1. 前言 <canvas>是HTML5新增元素,它是一个画板,开发人员基于它的2D上下文或webgl上下文,使用JS脚本绘制简单的动画、可交互画面,甚至进行视频渲染。 本篇介绍基于canvas的2D上下文绘制2D画面的一些方法和属性。 2. canvas…...

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

3DV 2024 Oral | SlimmeRF:可动态压缩辐射场,实现模型大小和建模精度的灵活权衡
目前大多数NeRF模型要么通过使用大型模型来实现高精度,要么通过牺牲精度来节省内存资源。这使得任何单一模型的适用范围受到局限,因为高精度模型可能无法适应低内存设备,而内存高效模型可能无法满足高质量要求。为此,本文研究者提…...

【unity学习笔记】4.场景切换
创建空物体→创建脚本挂载在空物体上→打开脚本 1.创建所需要的场景 assets中点击创建场景 2.文件→生成设置 3.将需要的场景拖入 4.场景跳转 创建空对象,将脚本放在空对象上。 注意两个类:场景类、场景管理类 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、微服务概念 微服务是一种非常流行的架构风格。 拒绝大型单体应用,基于业务边界进行服务微化拆分,各个服务独立部署运行。 每个服务运行在自己的单个进程使用轻量级机制通信可以使用不同的编程语言编写以及不同的数据存储技术 2、集群&分布式&…...
K8s之声明式APIs
大家好,我是升仔 引言 Kubernetes(K8s)是一个开源的容器编排系统,用于自动化部署、扩展和管理容器化应用。在K8s中,声明式APIs(Application Programming Interfaces)是一种核心概念࿰…...

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

Leetcode—62.不同路径【中等】
2023每日刷题(七十二) 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…...

【汇编笔记】初识汇编-内存读写
汇编语言的由来: CPU是计算机的核心,由于计算机只认识二进制,所以CPU执行的指令是二进制。 我们要想让CPU工作,就得给他提供它认识的指令,这一系列的指令的集合,称之为指令集。 指令集: 不同的体…...

Shell脚本通过渗透测试检测服务器安全!
以下是一个简单的 Shell 脚本通过渗透测试来发现服务器漏洞的例子: #!/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 存储结构: 3.1.3 二叉排序树的查找 3.1.4 二叉排序树的插入 3.1.5 二叉排序树删除 3.2 平衡二叉树(AVL 3.2.1 为什么要有平衡二叉树 3.2.2 定义 3.3 B-树 3.3.1…...

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

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

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

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

基于openGauss5.0.0全密态数据库等值查询小案例
基于openGauss5.0.0全密态数据库等值查询小案例 一、全密态数据库简介二、环境说明三、测试步骤四、使用约束 一、全密态数据库简介 价值体现: 密态数据库意在解决数据全生命周期的隐私保护问题,使得系统无论在何种业务场景和环境下,数据在传…...
Oracle中varchar2和nvarchar2的区别
Oracle中的varchar2和nvarchar2都是可变长度的字符数据类型,这意味着它们能够根据实际存储的数据长度来动态调整占用的空间。但它们之间有以下主要区别: 1. 字符编码和存储: - VARCHAR2:存储的是字节字符串,对字符…...

Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》
引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...
线程同步:确保多线程程序的安全与高效!
全文目录: 开篇语前序前言第一部分:线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分:synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分ÿ…...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

uniapp微信小程序视频实时流+pc端预览方案
方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度WebSocket图片帧定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐RTMP推流TRTC/即构SDK推流❌ 付费方案 (部分有免费额度&#x…...
Matlab | matlab常用命令总结
常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...
探索Selenium:自动化测试的神奇钥匙
目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...

【深度学习新浪潮】什么是credit assignment problem?
Credit Assignment Problem(信用分配问题) 是机器学习,尤其是强化学习(RL)中的核心挑战之一,指的是如何将最终的奖励或惩罚准确地分配给导致该结果的各个中间动作或决策。在序列决策任务中,智能体执行一系列动作后获得一个最终奖励,但每个动作对最终结果的贡献程度往往…...
32单片机——基本定时器
STM32F103有众多的定时器,其中包括2个基本定时器(TIM6和TIM7)、4个通用定时器(TIM2~TIM5)、2个高级控制定时器(TIM1和TIM8),这些定时器彼此完全独立,不共享任何资源 1、定…...