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

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录

ASP.NET Core 是一个跨平台的开源框架&#xff0c;用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录&#xff0c;以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代&#xff0c;加密货币作为一种新兴的金融现象&#xff0c;正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而&#xff0c;加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下&#xff0c;稳定…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...

Java毕业设计:WML信息查询与后端信息发布系统开发

JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发&#xff0c;实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构&#xff0c;服务器端使用Java Servlet处理请求&#xff0c;数据库采用MySQL存储信息&#xff0…...

uniapp手机号一键登录保姆级教程(包含前端和后端)

目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号&#xff08;第三种&#xff09;后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...

接口自动化测试:HttpRunner基础

相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具&#xff0c;支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议&#xff0c;涵盖接口测试、性能测试、数字体验监测等测试类型…...