当前位置: 首页 > 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;…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

管理学院权限管理系统开发总结

文章目录 &#x1f393; 管理学院权限管理系统开发总结 - 现代化Web应用实践之路&#x1f4dd; 项目概述&#x1f3d7;️ 技术架构设计后端技术栈前端技术栈 &#x1f4a1; 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 &#x1f5c4;️ 数据库设…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表

##鸿蒙核心技术##运动开发##Sensor Service Kit&#xff08;传感器服务&#xff09;# 前言 在运动类应用中&#xff0c;运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据&#xff0c;如配速、距离、卡路里消耗等&#xff0c;用户可以更清晰…...

网站指纹识别

网站指纹识别 网站的最基本组成&#xff1a;服务器&#xff08;操作系统&#xff09;、中间件&#xff08;web容器&#xff09;、脚本语言、数据厍 为什么要了解这些&#xff1f;举个例子&#xff1a;发现了一个文件读取漏洞&#xff0c;我们需要读/etc/passwd&#xff0c;如…...

嵌入式学习笔记DAY33(网络编程——TCP)

一、网络架构 C/S &#xff08;client/server 客户端/服务器&#xff09;&#xff1a;由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序&#xff0c;负责提供用户界面和交互逻辑 &#xff0c;接收用户输入&#xff0c;向服务器发送请求&#xff0c;并展示服务…...

计算机基础知识解析:从应用到架构的全面拆解

目录 前言 1、 计算机的应用领域&#xff1a;无处不在的数字助手 2、 计算机的进化史&#xff1a;从算盘到量子计算 3、计算机的分类&#xff1a;不止 “台式机和笔记本” 4、计算机的组件&#xff1a;硬件与软件的协同 4.1 硬件&#xff1a;五大核心部件 4.2 软件&#…...

如何通过git命令查看项目连接的仓库地址?

要通过 Git 命令查看项目连接的仓库地址&#xff0c;您可以使用以下几种方法&#xff1a; 1. 查看所有远程仓库地址 使用 git remote -v 命令&#xff0c;它会显示项目中配置的所有远程仓库及其对应的 URL&#xff1a; git remote -v输出示例&#xff1a; origin https://…...

FOPLP vs CoWoS

以下是 FOPLP&#xff08;Fan-out panel-level packaging 扇出型面板级封装&#xff09;与 CoWoS&#xff08;Chip on Wafer on Substrate&#xff09;两种先进封装技术的详细对比分析&#xff0c;涵盖技术原理、性能、成本、应用场景及市场趋势等维度&#xff1a; 一、技术原…...

shell脚本质数判断

shell脚本质数判断 shell输入一个正整数,判断是否为质数(素数&#xff09;shell求1-100内的质数shell求给定数组输出其中的质数 shell输入一个正整数,判断是否为质数(素数&#xff09; 思路&#xff1a; 1:1 2:1 2 3:1 2 3 4:1 2 3 4 5:1 2 3 4 5-------> 3:2 4:2 3 5:2 3…...

算法刷题-回溯

今天给大家分享的还是一道关于dfs回溯的问题&#xff0c;对于这类问题大家还是要多刷和总结&#xff0c;总体难度还是偏大。 对于回溯问题有几个关键点&#xff1a; 1.首先对于这类回溯可以节点可以随机选择的问题&#xff0c;要做mian函数中循环调用dfs&#xff08;i&#x…...