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

【遍历】非递归法 二叉树的前中后序遍历

文章目录

    • 非递归法
      • 前序遍历
      • 后序遍历
      • 中序遍历
    • 递归法DFS

非递归法

通过栈Stack来模拟递归。

前序遍历

LeetCode 144
在这里插入图片描述

前序遍历:1 2 3

定义:存放答案的List、栈Stack

  1. 将root入栈
  2. 出栈:node,为null则舍弃
  3. 将node放入list
  4. 将node.right入栈
  5. 将node.left入栈
  6. 栈不为空则重复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。

  1. cur = root
  2. cur不为空或者栈不为空
  3. 循环 将cur入栈,并将cur赋值其左节点,直到为空
  4. 出站node,将node加入list
  5. 将node赋值为node.left
  6. 重复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 前序遍历&#xff1a;1 2 3 定义&#xff1a;存放答案的List、栈Stack 将root入栈出栈&#xff1a;node&#xff0c;为null则舍弃将node放入list将node.r…...

Python将tiff转换成png

文章目录 问题描述解决方案压缩并转换参考文献 问题描述 base64 的 image/tiff 无法在页面直接展示&#xff0c;将其转换为 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 环境...

能够完成两个数的算术运算的单地址指令,地址码指明一个操作数,另一个操作数来自( )方式

【计算机组成原理错题】能够完成两个数的算术运算的单地址指令,地址码指明一个操作数&#xff0c;另一个操作数来自( )方式。 A.立即寻址 B.隐含寻址 C.间接寻址 D.基址寻址 正确答案&#xff1a;B 因为另一个操作数来自于累加器ACC&#xff0c;而这种方式属于隐含寻址。 在指令…...

数据库数据恢复-Oracle数据库数据恢复案例

数据库数据恢复环境&#xff1a; Oracle数据库ASM磁盘组有4块成员盘。 数据库故障&分析&#xff1a; Oracle数据库ASM磁盘组掉线 &#xff0c;ASM实例无法挂载&#xff0c;用户联系我们要求恢复oracle数据库。 数据库数据恢复工程师拿到磁盘后&#xff0c;先将所有磁盘以只…...

对于msvcr120.dll丢失的问题,分享几种解决方法

msvcr120.dll的作用是提供一系列的运行时函数和功能&#xff0c;以便应用程序能够正常运行。这些函数和功能包括内存管理、异常处理、输入输出操作、数学运算等。在没有这个库文件的情况下&#xff0c;应用程序可能无法正常启动或执行特定的功能&#xff0c;甚至会出现错误提示…...

网络安全进阶学习第十三课——SQL注入Bypass姿势

文章目录 一、等号被过滤二、substr、mid等被过滤三、逗号被过滤四、and/or被过滤五、空格被过滤五、其他绕过方式 一、等号被过滤 1、like&#xff0c;rlike语句&#xff0c;其中rlike是正则2、大于号>&#xff0c;小于号<3、符号<>&#xff1a;<>为不等于…...

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笔记-数据迁移(导出/导入)

这里先说明以下几点&#xff1a; Neo4j在4.0下版本默认的库名是&#xff1a;graph.db Neo4j在4.0上版本默认的库名是&#xff1a;neo4j.db 不管是Neo4j&#xff0c;还是Neo4j Desktop&#xff0c;都会在bin目录下有neo4j、neo4j-admin软件。在conf目录下&#xff0c;有neo4j.…...

请求转发和请求重定向

目录 1. 定义层面 2. 请求方层面 3. 数据共享层面 4. 最终 url 层面 5. 代码实现层面 请求转发 请求重定向 在Java中&#xff0c;跳转网页的方式有两种&#xff0c;一种是请求转发&#xff0c;另一种是请求重定向&#xff0c;而实际上&#xff0c;这两种方式是有着明显…...

TOMCAT的多实例部署和动静分离

tomcat的多实例 动静分离 排错小工具&#xff1a; telnet工具&#xff1a;yum -y install telnet telnet工具用于测试端口是否正常 telnet 20.0.0.101 80Tomcat多实例部署&#xff1a; 一台服务器上有多个tomcat的服务 1.安装好 jdk 2.安装 tomcat cd /opt tar zxvf apache-…...

阿里微服务seata组件tc告诉rm进行提交的时候,rm提交失败了seata怎么办呢?

当Seata的TC&#xff08;Transaction Coordinator&#xff09;向RM&#xff08;Resource Manager&#xff09;发起提交请求时&#xff0c;如果RM提交失败&#xff0c;Seata会采取以下步骤处理&#xff1a; 重试机制&#xff1a;Seata会尝试多次向RM发送提交请求&#xff0c;以确…...

已解决 RuntimeError: There is no current event loop in thread ‘Thread-1‘.

作者主页&#xff1a;爱笑的男孩。的博客_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平台搭建总结 前言 还是项目需要&#xff0c;暂时搭建安卓的运行平台。 Android平台搭建 安装包 双击安装包&#xff0c;进入安装。 下一步 根据自己需求&a…...

Python测试框架pytest:常用参数、查找子集、参数化、跳过

Pytest是一个基于python的测试框架&#xff0c;用于编写和执行测试代码。pytest主要用于API测试&#xff0c;可以编写代码来测试API、数据库、UI等。 pytest是一个非常成熟的全功能的Python测试框架&#xff0c;主要有以下几个优点&#xff1a; 简单灵活&#xff0c;容易上手。…...

Android 13 Hotseat定制化修改

一.背景 由于需求是需要自定义修改Hotseat,所以此篇文章是记录如何自定义修改hotseat的,应该可以覆盖大部分场景,修改点有修改hotseat布局方向,hotseat图标数量,hotseat图标大小,hotseat布局位置,hotseat图标禁止形成文件夹,hotseat图标禁止移动到Launcher中,下面开始…...

【VUE】7、VUE项目中集成watermark实现页面添加水印

在网站浏览中&#xff0c;常常需要网页水印&#xff0c;以便防止用户截图或录屏暴露敏感信息后&#xff0c;方便追踪用户来源。 1、安装 watermark 在 package.json 文件 dependencies 节点增加 watermark-dom 依赖 "watermark-dom": "2.3.0"然后执行命…...

Rider无法识别Todo Comment

最近因为vs code很难识别到代码中的usage和definition&#xff0c;改用Rider了。 但是一开始就哪里有点不对&#xff0c; 比如我主题的颜色总是有些地方无法识别出来。比如我每次从Unity中点击脚本文件&#xff0c;都只能识别到某一个特定的文件夹&#xff0c;而不能打开整个…...

用 docker 创建 jmeter 容器,能做性能测试?

我们都知道&#xff0c;jmeter 可以做接口测试&#xff0c;也可以用于性能测试&#xff0c;现在企业中性能测试也大多使用 jmeter。docker 是最近这些年流行起来的容器部署工具&#xff0c;可以创建一个容器&#xff0c;然后把项目放到容器中&#xff0c;就可以构建出一个独立的…...

Token 失效退出至登录页面

目录 前端设置&#xff1a; 1. 在登录页面&#xff0c;调用登录的接口后&#xff0c;直接获取当前时间并保存在本地&#xff0c;类似保存token。 2. 在路由守卫 获取本机存储的时间戳&#xff0c;加15分钟与当前时间进行对比&#xff0c;如果大于当前时间说明token失效&…...

Java 8 Stream API 入门到实践详解

一、告别 for 循环&#xff01; 传统痛点&#xff1a; Java 8 之前&#xff0c;集合操作离不开冗长的 for 循环和匿名类。例如&#xff0c;过滤列表中的偶数&#xff1a; List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...

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…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

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

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

浪潮交换机配置track检测实现高速公路收费网络主备切换NQA

浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求&#xff0c;本次涉及的主要是收费汇聚交换机的配置&#xff0c;浪潮网络设备在高速项目很少&#xff0c;通…...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障

关键领域软件测试的"安全密码"&#xff1a;Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力&#xff0c;从金融交易到交通管控&#xff0c;这些关乎国计民生的关键领域…...