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

二叉树的中序遍历,力扣

目录

题目地址:

题目:

解题方法:

解题分析:

解题思路:

代码实现:

注:

代码实现(递归):

代码实现(迭代):


题目地址:

94. 二叉树的中序遍历 - 力扣(LeetCode)

难度:简单

今天刷二叉树的中序遍历,大家有兴趣可以点上看看题目要求,试着做一下

题目:

给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。

我们直接看题解吧:

解题方法:

方法1,递归

方法2,迭代

方法3,Morris(空间复杂度(1))

解题分析:

中序遍历顺序:左子树->根节点->右子树(即左根右)

递归方法通俗易懂,但效率低,迭代方法,效率虽高,但不易理解,

因此这里着重讲一下Morris方法。

解题思路:

设当前遍历节点为x:

1、若x无左孩子,将x的值放入答案数组,接着访问x右孩子,即x=x.right。

2、若x有左孩子,则找到该左子树中最右的节点(即左子树中序遍历的最后一个节点)记为predecessor。

    · 若predecessor的右孩子为空,则将右孩子指向x,接着访问x左孩子即x=x.left

     ·若predecessor的右孩子不为空,则将右孩子指向x,此时说明已遍历完x的左子树,则将predecessor的右孩子置空,将x的值加入答案数组,然后访问x的右孩子即x=x.right

3、重复上述操作,直至访问完整棵树。

 具体可结合题解-->  :94. 二叉树的中序遍历 题解

代码实现:

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<Integer>(); //创建集合存储节点的值TreeNode predecessor = null;   //创建predxessor节点,并置空while (root != null) {if (root.left != null) {//左孩子不为空// predecessor 节点就是当前 root 节点向左走一步,然后一直向右走至无法走为止predecessor = root.left;while (predecessor.right != null && predecessor.right != root) {predecessor = predecessor.right;}// 让 predecessor 的右指针指向 root,继续遍历左子树if (predecessor.right == null) {predecessor.right = root;root = root.left;}// 说明左子树已经访问完了,我们需要断开链接else {res.add(root.val);predecessor.right = null;root = root.right;}}// 如果没有左孩子,则直接访问右孩子else {res.add(root.val);root = root.right;}}return res;}
}
注:

其实整个过程我们就多做一步:假设当前遍历到的节点为 x,将 x 的左子树中最右边的节点的右孩子指向 x,这样在左子树遍历完成后我们通过这个指向走回了 x,且能通过这个指向知晓我们已经遍历完成了左子树,而不用再通过栈来维护,省去了栈的空间复杂度。

代码实现(递归):

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<Integer>();inorder(root, res);return res;}public void inorder(TreeNode root, List<Integer> res) {if (root == null) {return;}inorder(root.left, res);res.add(root.val);inorder(root.right, res);}
}

代码实现(迭代):

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<Integer>();Deque<TreeNode> stk = new LinkedList<TreeNode>();while (root != null || !stk.isEmpty()) {while (root != null) {stk.push(root);root = root.left;}root = stk.pop();res.add(root.val);root = root.right;}return res;}
}

相关文章:

二叉树的中序遍历,力扣

目录 题目地址&#xff1a; 题目&#xff1a; 解题方法&#xff1a; 解题分析&#xff1a; 解题思路&#xff1a; 代码实现&#xff1a; 注&#xff1a; 代码实现&#xff08;递归&#xff09;&#xff1a; 代码实现&#xff08;迭代&#xff09;&#xff1a; 题目地址&#xf…...

shiro1.10版本后-IniSecurityManagerFactory过期失效

1、问题概述&#xff1f; 今天在研究了shiro的新版本shiro1.13.0版本&#xff0c;发现用了很长时间的IniSecurityManagerFactory工厂失效了。 从下图中可以看出&#xff0c;在新版本中IniSecurityManagerFactory被打上了过期线了。 那么问题来了&#xff0c;新版本如何使用呢…...

阿里后端实习二面

阿里后端实习二面 记录面试题目&#xff0c;希望可以帮助到大家 类加载的流程&#xff1f; 类加载分为三个部分&#xff1a;加载、连接、初始化 加载 类的加载主要的职责为将.class文件的二进制字节流读入内存(JDK1.7及之前为JVM内存&#xff0c;JDK1.8及之后为本地内存)&…...

「Kafka」生产者篇

「Kafka」生产者篇 生产者发送消息流程 在消息发送的过程中&#xff0c;涉及到了 两个线程 ——main 线程和Sender 线程。 在 main 线程中创建了 一个 双端队列 RecordAccumulator。 main线程将消息发送给RecordAccumulator&#xff0c;Sender线程不断从 RecordAccumulator…...

C语言实现RSA算法加解密

使用c语言实现了RSA加解密算法&#xff0c;可以加解密文件和字符串。 rsa算法原理 选择两个大素数p和q&#xff1b;计算n p * q;计算φ(n)(p-1)(q-1)&#xff1b;选择与φ(n)互素的整数d&#xff1b;由de1 mod φ(n)计算得到e&#xff1b;公钥是(e, n), 私钥是(d, n);假设明…...

如何设计前后端分离的系统架构?

如何将前端页面和后端Java代码进行集成&#xff1f; 将前端页面和后端Java代码进行集成通常需要使用一些特定的工具和技术。以下是一些常见的方法&#xff1a; 使用RESTful API&#xff1a;REST&#xff08;Representational State Transfer&#xff09;是一种基于HTTP协议构…...

【强化学习】SARAS代码实现

前言 SARAS&#xff0c;假设环境状态和动作状态都是离散的。利用动作价值矩阵来进行行为的预测。其主要就是利用时序差分的思想&#xff0c;对动作价值矩阵进行更新。 代码实现 import gymnasium as gym import numpy as npclass sarsa():def __init__(self, states_n, acti…...

P1019 [NOIP2000 提高组] 单词接龙 刷题笔记

P1019 [NOIP2000 提高组] 单词接龙 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 思路来自 大佬 Chardo 的个人中心 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 匹配 &#xff1a; 将 第一个字符串末尾 和第二个字符串第一个开始匹配 如果 j<i这段走完了 flag还没…...

如何实现WinApp的UI自动化测试?

WinApp&#xff08;WindowsAPP&#xff09;是运行在Windows操作系统上的应用程序&#xff0c;通常会提供一个可视的界面&#xff0c;用于和用户交互。例如运行在Windows系统上的Microsoft Office、PyCharm、Visual Studio Code、Chrome&#xff0c;都属于WinApp。常见的WinApp&…...

chrome扩展程序开发之在目标页面运行自己的JS

原文地址&#xff1a;https://qdgithub.com/home/index/article/aid/247.html chrome 插件开发的入门介绍&#xff0c;实现利用 chrome 扩展实现在目标网页运行我们的 js 的功能。关于 chrome 扩展的详细内容&#xff0c;可以通过官网了解。 开发工具很简单&#xff0c;记事本…...

NLP项目之语种识别

目录 1. 代码及解读2. 知识点n-grams仅保留最常见的1000个n-grams。意思是n1000 ? 1. 代码及解读 in_f open(data.csv) lines in_f.readlines() in_f.close() dataset [(line.strip()[:-3], line.strip()[-2:]) for line in lines] print(dataset[:5])[(1 december wereld…...

Linux lpr命令教程:如何使用lpr命令打印文件(附案例详解和注意事项)

Linux lpr命令介绍 lpr命令在Unix-like操作系统中用于提交打印任务。如果在命令行中指定了文件名&#xff0c;那么这些文件将被发送到指定的打印机&#xff08;如果没有指定目的地&#xff0c;则发送到默认目的地&#xff09;。如果命令行中没有列出文件&#xff0c;lpr将从标…...

浅谈C语言inline关键字

对于C开发者来说&#xff0c;inline是个再熟悉不过的关键字&#xff0c;因为默认的成员函数都是inline&#xff0c;也是常规高校教材中宣扬C的“优势”之一。 但是C语言其实也是支持inline关键字的&#xff0c;而且是很早期的gcc就支持了该关键字。在Linux0.12版本内核代码中也…...

Flink1.17实战教程(第六篇:容错机制)

系列文章目录 Flink1.17实战教程&#xff08;第一篇&#xff1a;概念、部署、架构&#xff09; Flink1.17实战教程&#xff08;第二篇&#xff1a;DataStream API&#xff09; Flink1.17实战教程&#xff08;第三篇&#xff1a;时间和窗口&#xff09; Flink1.17实战教程&…...

OpenCV实战 -- 维生素药片的检测记数

文章目录 检测记数原图经过操作开始进行消除粘连性--形态学变换总结实现方法1. 读取图片&#xff1a;2. 形态学处理&#xff1a;3. 二值化&#xff1a;4. 提取轮廓&#xff1a;5. 轮廓筛选和计数&#xff1a; 分水岭算法&#xff1a;逐行解释在基于距离变换的分水岭算法中&…...

【AI】注意力机制与深度学习模型

目录 一、注意力机制 二、了解发展历程 2.1 早期萌芽&#xff1a; 2.2 真正意义的注意力机制&#xff1a; 2.3 2015 年及以后&#xff1a; 2.4 自注意力与 Transformer&#xff1a; 2.5 BERT 与预训练模型&#xff1a; 三、基本框架 1. 打分函数&#xff08;Score Fun…...

HTML5和JS实现新年礼花效果

HTML5和JS实现新年礼花效果 2023兔年再见&#xff0c;2024龙年来临了&#xff01; 祝愿读者朋友们在2024年里&#xff0c;身体健康&#xff0c;心灵愉悦&#xff0c;梦想成真。 下面是用HTML5和JS实现新年礼花效果&#xff1a; 源码如下&#xff1a; <!DOCTYPE html>…...

【owt-server】一些构建项目梳理

【owt-server】清理日志&#xff1a;owt、srs、ffmpeg 【owt】p2p client mfc 工程梳理【m98】webrtc vs2017构建带符号的debug库【OWT】梳理构建的webrtc和owt mfc工程 m79的mfc客户端及owt-client...

Linux shell编程学习笔记38:history命令

目录 0 前言 1 history命令的功能、格式和退出状态1.1 history命令的功能1.2 history命令的格式1.3退出状态2 命令应用实例2.1 history&#xff1a;显示命令历史列表2.2 history -a&#xff1a;将当前会话的命令行历史追加到历史文件~/.bash_history中2.3 history -c&#xf…...

elasticsearch安装教程(超详细)

1.1 创建网络&#xff08;单点部署&#xff09; 因为我们还需要部署 kibana 容器&#xff0c;因此需要让 es 和 kibana 容器互联&#xff0c;所有先创建一个网络&#xff1a; docker network create es-net 1.2.加载镜像 采用的版本为 7.12.1 的 elasticsearch&#xff1b;…...

MPNet:旋转机械轻量化故障诊断模型详解python代码复现

目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

pam_env.so模块配置解析

在PAM&#xff08;Pluggable Authentication Modules&#xff09;配置中&#xff0c; /etc/pam.d/su 文件相关配置含义如下&#xff1a; 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块&#xff0c;负责验证用户身份&am…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...

MinIO Docker 部署:仅开放一个端口

MinIO Docker 部署:仅开放一个端口 在实际的服务器部署中,出于安全和管理的考虑,我们可能只能开放一个端口。MinIO 是一个高性能的对象存储服务,支持 Docker 部署,但默认情况下它需要两个端口:一个是 API 端口(用于存储和访问数据),另一个是控制台端口(用于管理界面…...