非递归遍历二叉树(数据结构)

我的博客主页在这里插入图片描述

非递归遍历二叉树

  • 前序遍历(迭代)
  • 中序遍历(迭代)
  • 后续遍历(迭代)

二叉树的遍历方式有:前序遍历、中序遍历、后续遍历,层序遍历,而树的大部分情况下都是通过递归的方式来进行的。
首先要明白递归是函数自身调用自身,设计了很多因素记录树中遍历的入栈 记录地址等。。。因为是在栈上开辟空间,这些操作对于时间和空间的消耗会更大,且容易溢出。迭代(非递归)它是在栈堆中开辟更大的空间,不容易溢出,且不会调用函数自身,效率也会提升很多。

更多的二叉树的oj题目在我的专栏中,感谢大家的观看

在数据结构中的学习难免少不了递归的学习,递归有时候也会让代码变得更加简洁,学习递归让我们对代码有更近一步的思考。

前序遍历(迭代)

每遍历一个节点打印一次元素且将其放入栈中,直到为空时,将栈顶元素移除来并打印并让其查看另一子树是否为空节点。
在这里插入图片描述

   public static void preOrderIteration(TreeNode root){if(root==null)return ;//根节点没有属性Stack<TreeNode> stack=new Stack<>();TreeNode cur=root;while(cur!=null||!stack.isEmpty()){while(cur!=null){stack.push(cur);System.out.print(cur.val+" ");cur=cur.left;}cur=stack.pop();//将从栈中弹出的元素给到curcur=cur.right;//cur的右边赋值给cur是否为空}}

中序遍历(迭代)

因为中序遍历是左根右,给定一个辅助栈,每次走到最后一个节点的left或者right为空时将栈中的元素给到数组,然后再去遍历栈顶右边元素是否为空。
在这里插入图片描述

public List<Integer> inorderTraversal(TreeNode root) {List<Integer> list=new LinkedList<>();Stack<TreeNode> stack=new Stack<>();while(root!=null||!stack.isEmpty()){if(root!=null){stack.push(root);root=root.left;}else{//如果为null说明该节点的左子树为空,将栈顶元素放入数组中list.add(stack.peek().val);//检查栈顶的右节点root = stack.pop().right;}}return list;}

后续遍历(迭代)

在这里插入图片描述

   public List<Integer> postorderTraversal(TreeNode root) {List<Integer> list=new LinkedList<>();if(root==null)return list;Stack<TreeNode> stack=new Stack<>();TreeNode prev=null;//记录上一个移除栈的元素while(root!=null||!stack.isEmpty()){while(root!=null){stack.push(root);root=root.left;}TreeNode top = stack.peek();//查看顶部元素右树是否为空//两个条件,右树为null或者此元素右树已经出过栈则直接出栈if(top.right==null||prev==top.right){TreeNode cur = stack.pop();list.add(cur.val);prev=top;//记录上一个栈顶元素}else{root=top.right;}}return list;}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/480302.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【CSS】一篇掌握CSS

不是因为有了希望才去坚持,而是坚持了才有了希望 目录 一.导入方式 1.行内样式 2.内部样式 3.外部样式(常用) 二.选择器 1.基本选择器(常用) 1.1标签选择器 1.2类选择器 1.3id选择器 2.层次选择器 2.1后代选择器 2.2子选择器 2.3相邻兄弟选择器 2.4通用兄弟选择器…

封装类与封装函数

目录结构 src/ ├── utils/ │ ├── test.js │ ├── Calculator.js ├── views/ │ ├── Home.vue ├── App.vue 共同点&#xff1a;模块导出与模块引入 封装函数 场景 简单、轻量级和性能敏感的场景&#xff0c;适合快速开发和维护。 优 可维护性&…

【论文阅读】Federated learning backdoor attack detection with persistence diagram

目的&#xff1a;检测联邦学习环境下&#xff0c;上传上来的模型是不是恶意的。 1、将一个模型转换为|L|个PD,&#xff08;其中|L|为层数&#xff09; 如何将每一层转换成一个PD&#xff1f; 为了评估第&#x1d457;层的激活值&#xff0c;我们需要&#x1d450;个输入来获…

5 Java字符串操作

字符串操作 1、String类1.1 声明字符串1.2 创建字符串 1.3 字符串连接 /连接字符串连接其他数据类型 1.4 提取字符串信息获取字符串长度length()获取指定位置的字符 charAt()获取子字符串索引位置 indexOf()判断字符串首尾内容 startsWith()/endsWith()获取字符数组 toCharArra…

IDEA报错: java: JPS incremental annotation processing is disabled 解决

起因 换了个电脑打开了之前某个老项目IDEA启动springcloud其中某个服务直接报错&#xff0c;信息如下 java: JPS incremental annotation processing is disabled. Compilation results on partial recompilation may be inaccurate. Use build process “jps.track.ap.depen…

Mybatis-基础操作

Mybatis的基础操作就是通过Mybatis完成对数据的增删改查。我们通过例子来引入这些操作&#xff0c;之前的项目较久远&#xff0c;因此我们从零开始进行准备工作&#xff1a; 搭建项目 一、创建数据库user_list并插入数据&#xff1a; -- 创建数据库 create table user_list …

火山引擎VeDI在AI+BI领域的演进与实践

随着数字化时代的到来&#xff0c;企业对于数据分析与智能决策的需求日益增强。作为新一代企业级数据智能平台&#xff0c;火山引擎数智平台VeDI基于字节跳动多年的“数据驱动”实践经验&#xff0c;也正逐步在AI&#xff08;人工智能&#xff09;与BI&#xff08;商业智能&…

鼠标前进后退键改双击,键盘映射(AutoHotkey)

初衷&#xff1a; 1.大部分鼠标为不可自定义按键&#xff0c;可以自定义的又很贵。 鼠标左键是双击是很频类很高的操作&#xff0c;鼠标前进/后退按键个人感觉使用频率很低&#xff0c;因此把鼠标前进/后退改为双击还是很合适的。 2.有些短款的键盘没有Home或End键&#xff0c;…

IntelliJ IDEA安装内网穿透实现远程连接家里或公司的MySQL数据库助力开发

文章目录 前言1. 本地连接测试2. Windows安装Cpolar3. 配置Mysql公网地址4. IDEA远程连接Mysql5. 固定连接公网地址6. 固定地址连接测试 前言 本教程主要介绍如何使用Cpolar内网穿透工具实现在IDEA中也可以远程访问家里或者公司的数据库&#xff0c;提高开发效率&#xff01;无…

联想品牌的电脑 Bios 快捷键是什么?如何进入 Bios 设置?

在某些情况下&#xff0c;您可能需要通过U盘来安装操作系统或进行系统修复。对于联想电脑用户来说&#xff0c;了解如何设置U盘作为启动设备是非常有用的技能之一。本文简鹿办公将指导您如何使用联想电脑的 U 盘启动快捷键来实现这一目标。 联想笔记本 对于大多数联想笔记本电…

MCU跨领域融合的风向标是什么?

【哔哥哔特导读】从市场竞争的加剧到技术发展的需求&#xff0c;从智能化趋势到安全性要求的提高&#xff0c;再到市场需求的变化&#xff0c;这些因素共同推动了MCU趋势的发展&#xff0c;那么&#xff0c;当前的发展方向是怎样的&#xff1f; 随着技术的飞速发展和市场需求的…

【Android+多线程】IntentService 知识总结:应用场景 / 使用步骤 / 源码分析

定义 IntentService 是 Android中的一个封装类&#xff0c;继承自四大组件之一的Service 功能 处理异步请求 & 实现多线程 应用场景 线程任务 需 按顺序、在后台执行 最常见的场景&#xff1a;离线下载不符合多个数据同时请求的场景&#xff1a;所有的任务都在同一个T…

AI自动化剪辑工具:可将长视频中精彩部分提取合成短视频

最近&#xff0c;我发现了一款特别适合当下短视频潮流的自动化工具&#xff0c;它能够让我们轻松从长视频中剪辑出精彩片段&#xff0c;并快速生成适合分享的短视频。 这款工具叫 AI Youtube Shorts Generator&#xff0c;是一个开源项目&#xff0c;特别适合那些喜欢制作短视…

Basemap 在地图上显示图例

1.卫星图像绘制 import matplotlib.pyplot as plt from mpl_toolkits.basemap import Basemap # 图像绘制 plt.figure(dpi300) m Basemap(projectioncyl, llcrnrlat11, llcrnrlon105, urcrnrlat35, urcrnrlon135)raw_lat raw_lat[490:1080, 655:1470] raw_lon raw_lon[490:…

GitLab历史演进

GitLab 是一个基于 Git 的 DevOps 平台&#xff0c;它的历史演进反映了开发和运维协作工具的不断发展。GitLab 的目标是为开发团队提供一个集成的工具集&#xff0c;涵盖 源代码管理、CI/CD、项目管理 等功能。GitLab 最初只是一个 Git 仓库管理工具&#xff0c;但随着时间的推…

elasticsearch单节点模式部署

原文地址&#xff1a;elasticsearch单节点模式部署 – 无敌牛 欢迎参观我的个人博客&#xff1a;无敌牛 – 技术/著作/典籍/分享等 第一步&#xff1a;下载 官方下载地址&#xff1a;Download Elasticsearch | Elastic&#xff0c;可以 wget 直接下载。 命令&#xff1a;wg…

26页PDF | 数据中台能力框架及评估体系解读(限免下载)

一、前言 这份报告详细解读了数据中台的发展历程、核心概念、能力框架及成熟度评估体系。它从阿里巴巴的“大中台&#xff0c;小前台”战略出发&#xff0c;探讨了数据中台如何通过整合企业内部的数据资源和能力&#xff0c;加速业务迭代、降低成本&#xff0c;并推动业务增长…

音视频入门基础:MPEG2-TS专题(8)——TS Header中的适配域

注&#xff1a;本文有部分内容引用了维基百科&#xff1a;https://zh.wikipedia.org/wiki/MPEG2-TS 一、引言 当TS Header中的adaptation_field_control属性的值为10或11 时&#xff0c;TS Header包含adaptation field&#xff08;适配域&#xff09;&#xff1a; 根据《T-RE…

挑战用React封装100个组件【001】

项目地址 https://github.com/hismeyy/react-component-100 组件描述 组件适用于需要展示图文信息的场景&#xff0c;比如产品介绍、用户卡片或任何带有标题、描述和可选图片的内容展示 样式展示 代码展示 InfoCard.tsx import ./InfoCard.cssinterface InfoCardProps {ti…

百度智能云千帆部署流程---语音识别和合成

目录 一、前期准备 二、语音合成 三、语音识别 实现整个流程如下图&#xff0c;但是我们的工作量并不是很多&#xff0c;我们可以在官网找到示例代码 一、前期准备 这里我们使用到3个代码 API_KEY.py 填写我们的API xzarm_asr.py 语音识别 xzarm_tts.py 语音合…