二叉树的中序遍历,力扣
目录
题目地址:
题目:
解题方法:
解题分析:
解题思路:
代码实现:
注:
代码实现(递归):
代码实现(迭代):
题目地址:
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;}
}
相关文章:
二叉树的中序遍历,力扣
目录 题目地址: 题目: 解题方法: 解题分析: 解题思路: 代码实现: 注: 代码实现(递归): 代码实现(迭代): 题目地址…...
shiro1.10版本后-IniSecurityManagerFactory过期失效
1、问题概述? 今天在研究了shiro的新版本shiro1.13.0版本,发现用了很长时间的IniSecurityManagerFactory工厂失效了。 从下图中可以看出,在新版本中IniSecurityManagerFactory被打上了过期线了。 那么问题来了,新版本如何使用呢…...
阿里后端实习二面
阿里后端实习二面 记录面试题目,希望可以帮助到大家 类加载的流程? 类加载分为三个部分:加载、连接、初始化 加载 类的加载主要的职责为将.class文件的二进制字节流读入内存(JDK1.7及之前为JVM内存,JDK1.8及之后为本地内存)&…...
「Kafka」生产者篇
「Kafka」生产者篇 生产者发送消息流程 在消息发送的过程中,涉及到了 两个线程 ——main 线程和Sender 线程。 在 main 线程中创建了 一个 双端队列 RecordAccumulator。 main线程将消息发送给RecordAccumulator,Sender线程不断从 RecordAccumulator…...
C语言实现RSA算法加解密
使用c语言实现了RSA加解密算法,可以加解密文件和字符串。 rsa算法原理 选择两个大素数p和q;计算n p * q;计算φ(n)(p-1)(q-1);选择与φ(n)互素的整数d;由de1 mod φ(n)计算得到e;公钥是(e, n), 私钥是(d, n);假设明…...
如何设计前后端分离的系统架构?
如何将前端页面和后端Java代码进行集成? 将前端页面和后端Java代码进行集成通常需要使用一些特定的工具和技术。以下是一些常见的方法: 使用RESTful API:REST(Representational State Transfer)是一种基于HTTP协议构…...
【强化学习】SARAS代码实现
前言 SARAS,假设环境状态和动作状态都是离散的。利用动作价值矩阵来进行行为的预测。其主要就是利用时序差分的思想,对动作价值矩阵进行更新。 代码实现 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) 匹配 : 将 第一个字符串末尾 和第二个字符串第一个开始匹配 如果 j<i这段走完了 flag还没…...
如何实现WinApp的UI自动化测试?
WinApp(WindowsAPP)是运行在Windows操作系统上的应用程序,通常会提供一个可视的界面,用于和用户交互。例如运行在Windows系统上的Microsoft Office、PyCharm、Visual Studio Code、Chrome,都属于WinApp。常见的WinApp&…...
chrome扩展程序开发之在目标页面运行自己的JS
原文地址:https://qdgithub.com/home/index/article/aid/247.html chrome 插件开发的入门介绍,实现利用 chrome 扩展实现在目标网页运行我们的 js 的功能。关于 chrome 扩展的详细内容,可以通过官网了解。 开发工具很简单,记事本…...
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操作系统中用于提交打印任务。如果在命令行中指定了文件名,那么这些文件将被发送到指定的打印机(如果没有指定目的地,则发送到默认目的地)。如果命令行中没有列出文件,lpr将从标…...
浅谈C语言inline关键字
对于C开发者来说,inline是个再熟悉不过的关键字,因为默认的成员函数都是inline,也是常规高校教材中宣扬C的“优势”之一。 但是C语言其实也是支持inline关键字的,而且是很早期的gcc就支持了该关键字。在Linux0.12版本内核代码中也…...
Flink1.17实战教程(第六篇:容错机制)
系列文章目录 Flink1.17实战教程(第一篇:概念、部署、架构) Flink1.17实战教程(第二篇:DataStream API) Flink1.17实战教程(第三篇:时间和窗口) Flink1.17实战教程&…...
OpenCV实战 -- 维生素药片的检测记数
文章目录 检测记数原图经过操作开始进行消除粘连性--形态学变换总结实现方法1. 读取图片:2. 形态学处理:3. 二值化:4. 提取轮廓:5. 轮廓筛选和计数: 分水岭算法:逐行解释在基于距离变换的分水岭算法中&…...
【AI】注意力机制与深度学习模型
目录 一、注意力机制 二、了解发展历程 2.1 早期萌芽: 2.2 真正意义的注意力机制: 2.3 2015 年及以后: 2.4 自注意力与 Transformer: 2.5 BERT 与预训练模型: 三、基本框架 1. 打分函数(Score Fun…...
HTML5和JS实现新年礼花效果
HTML5和JS实现新年礼花效果 2023兔年再见,2024龙年来临了! 祝愿读者朋友们在2024年里,身体健康,心灵愉悦,梦想成真。 下面是用HTML5和JS实现新年礼花效果: 源码如下: <!DOCTYPE html>…...
【owt-server】一些构建项目梳理
【owt-server】清理日志: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:显示命令历史列表2.2 history -a:将当前会话的命令行历史追加到历史文件~/.bash_history中2.3 history -c…...
elasticsearch安装教程(超详细)
1.1 创建网络(单点部署) 因为我们还需要部署 kibana 容器,因此需要让 es 和 kibana 容器互联,所有先创建一个网络: docker network create es-net 1.2.加载镜像 采用的版本为 7.12.1 的 elasticsearch;…...
arkts中@Watch监听的使用
概述 Watch用于监听状态变量的变化,当状态变量变化时,Watch的回调方法将被调用。Watch在ArkUI框架内部判断数值有无更新使用的是严格相等(),遵循严格相等规范。当在严格相等为false的情况下,就会触发Watch的…...
【Jmeter】Jmeter基础9-BeanShell介绍
3、BeanShell BeanShell是一种完全符合Java语法规范的脚本语言,并且又拥有自己的一些语法和方法。 3.1、Jmeter中使用的BeanShell 在Jmeter中,除了配置元件,其他类型的元件中都有BeanShell。BeanShell 是一种完全符合Java语法规范的脚本语言,并且又拥…...
详解数组的轮转
𝙉𝙞𝙘𝙚!!👏🏻‧✧̣̥̇‧✦👏🏻‧✧̣̥̇‧✦ 👏🏻‧✧̣̥̇:Solitary-walk ⸝⋆ ━━━┓ - 个性标签 - :来于“云”的“羽球人”。…...
html 表格 笔记
<!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>第二个页面</title><meta name"language" content"cn"> </head> <body><h2 sytle"width:500px;…...
计算机网络【HTTP 面试题】
HTTP的请求报文结构和响应报文结构 HTTP请求报文主要由请求行、请求头、空行、请求正文(Get请求没有请求正文)4部分组成。 1、请求行 由三部分组成,分别为:请求方法、URL以及协议版本,之间由空格分隔;请…...
linux基于用户身份对资源访问进行控制的解析及过程
linux中用户分为三类 1.超级用户(root) 拥有至高无上的权限 2.普通用户 人为创建、权限小,权限受到控制 3.程序用户 运行程序的用户,不是给人使用的,给程序使用的,一般不给登录! 组账…...
手动创建idea SpringBoot 项目
步骤一: 步骤二: 选择Spring initializer -> Project SDK 选择自己的JDK版本 ->Next 步骤三: Maven POM ->Next 步骤四: 根据JDK版本选择Spring Boot版本 11版本及以上JDK建议选用3.2版本,JDK为11版本…...
【Go语言入门:Go语言的数据结构】
文章目录 3.Go语言的数据结构:3.1. 指针3.2. struct(结构体)3.3. Map(映射,哈希) 3.Go语言的数据结构: 简介: 在Go语言中,数据结构体可以分为四种类型:基础类型、聚合类型、引用类型…...
QT designer的ui文件转py文件之后,实现pycharm中运行以方便修改逻辑,即添加实时模板框架
为PyCharm中的实时模板,你需要遵循以下步骤: 打开PyCharm的设置: 选择 File > Settings(在macOS上是 PyCharm > Preferences)。 导航到实时模板: 在设置中找到 Editor > Live Templates。 添加新的模板组 (可选): 为了…...
什么是负载均衡?
负载均衡是指在计算机网络领域中,将客户端请求分配到多台服务器上以实现带宽资源共享、优化资源利用率和提高系统性能的技术。负载均衡可以帮助小云有效解决单个服务器容量不足或性能瓶颈的问题,小云通过平衡流量负载,使得多台服务器能够共同…...
Python和Java的优缺点
Python的优点: 简单易学:Python的语法简洁清晰,易于学习和理解。丰富的库和框架:Python拥有庞大的标准库和活跃的开源社区,可以快速使用各种功能强大的库和框架,比如NumPy、Pandas、Django等。可读性强&am…...
AES - 在tiny-AES-c基础上封装了2个应用函数(加密/解密)
文章目录 AES - 在tiny-AES-c基础上封装了2个应用函数(加密/解密)概述增加2个封装函数的AES库aes.haes.c在官方测试程序上改的测试程序(用来测试这2个封装函数)END AES - 在tiny-AES-c基础上封装了2个应用函数(加密/解密) 概述 在github山有个星数很高的AES的C库 tiny-AES-c …...
51和32单片机读取FSR薄膜压力传感器压力变化
文章目录 简介线性电压转换模块51单片机读取DO接线方式51代码实验效果 32单片机读取AO接线方式32代码实验效果 总结 简介 FSR薄膜压力传感器是可以将压力变化转换为电阻变化的一种传感器,单片机可以读取然后作为粗略测量压力(仅提供压力变化,…...
【maven】pom.xml 文件详解
有关 maven 其他配置讲解参考 maven 配置文件 setting.xml 详解 pom.xml 文件是 Maven 项目的核心配置文件,其中包含了项目的元数据、构建配置、依赖管理等信息。以下是一个 pom.xml 文件的主要部分: <?xml version"1.0" encoding"U…...
SpringMVC源码解析——DispatcherServlet初始化
在Spring中,ContextLoaderListener只是辅助功能,用于创建WebApplicationContext类型的实例,而真正的逻辑实现其实是在DispatcherServlet中进行的,DispatcherServlet是实现Servlet接口的实现类。Servlet是一个JAVA编写的程序&#…...
搞定Apache Superset
踩雷了无数次终于解决了Superset的一系列问题 现在是北京时间2023年12月27日,亲测有效。 Superset概述 Apache Superset是一个现代的数据探索和可视化平台。它功能强大且十分易用,可对接各种数据源,包括很多现代的大数据分析引擎ÿ…...
【每日试题】java面试之ssm框架
以下是20道常见的SSM(SpringSpring MVCMyBatis)面试题目和答案: 什么是SSM框架? SSM是指SpringSpring MVCMyBatis的组合,它是Java Web开发中常用的轻量级框架集合。 介绍一下SSM框架各个组件的作用? Sprin…...
Flutter 疑难杂症集合
一. Flutter集成uni小程序sdk 1. 手机连接电脑测试打开uni小程序没问题,打包成apk后debug编译下的apk也没问题,但就是release编译的apk包打不开小程序。 报错情景:点击后页面会闪现一下黑色的背景,然后又跳转回了点击之前的页面。…...
PHP序列化总结1--序列化和反序列化的基础知识
序列化和反序列化的作用 1.序列化:将对象转化成数组或者字符串的形式 2.反序列化:将数组或字符串的形式转化为对象 为什么要进行序列化 这种数据形式中间会有很多空格,不同人有不同的书写情况,可能还会出现换行的情况 为此为了…...
【Linux】 last 命令使用
last 命令 用于检索和展示系统中用户的登录信息。它从/var/log/wtmp文件中读取记录,并将登录信息按时间顺序列出。 著者 Miquel van Smoorenburg 语法 last [-R] [-num] [ -n num ] [-adiox] [ -f file ] [name...] [tty...]last 命令 -Linux手册页 选项及作用…...
Git 分布式版本控制系统(序章1)
第一章 Git 分布式版本控制系统 为什么学Git? 某些企业面试需要掌握Git,同时,也方便管理自己的Qt项目。 一、Git 客户端下载(Windows) 下载地址 https://gitee.com/all-about-git#git-%E5%A4%A7%E5%85%A8 二、Git 的特点 分支…...
给WordPress网站添加返回顶部按钮
给WordPress网站底部添加一个按钮,点它就可以现实快速返回到顶部。有两种方法可以现实,一种是通过安装相关插件来实现。另外一种方式就是以纯属代码的方式来实现。 给WordPress网站底部添加一个按钮,点它就可以现实快速返回到顶部。有两种方…...
App Inventor 2 接入短信服务,实现短信验证码功能
发送短信验证码功能一般都是基于短信平台提供的sdk进行调用,这里是基于阿里云短信平台进行的开发,阿里云短信平台接入步骤请点此参考。 App Inventor 2拓展提供的函数如下: 主要提供2个函数,生成随机位数的数字随机码 和 发送短信…...
Linux环境grep搜索方法记录
1 grep grep 命令,用来搜索字符串所在位置,可以具体到不同文件,不同行; 在Linux 下,查看命令释义如下 zhaocubuntu2004:~$ grep --help Usage: grep [OPTION]... PATTERNS [FILE]... Search for PATTERNS in each FI…...
C语言-破解密码
题目描述 密码是我们生活中非常重要的东东,我们的那么一点不能说的秘密就全靠它了。哇哈哈. 接下来渊子要在密码之上再加一套密码,虽然简单但也安全。 假设老王原来一个BBS上的密码为zvbo941987,为了方便记忆,他通过一种算法把这个密码变换…...
ffmpeg 解码文件时的时间戳问题
实时流和普通文件 1 实时流 实时流编码时,我们一般不进行b帧编码,但是文件存储时为了减小大小,会增加b帧,实时流只带了I,P帧,那就会好很多 2 普通文件 很多文件带了b帧,所以要使用解码时间去同…...
Java企业电子招投标系统源代码,支持二次开发,采用Spring cloud框架
在数字化采购领域,企业需要一个高效、透明和规范的管理系统。通过采用Spring Cloud、Spring Boot2、Mybatis等先进技术,我们打造了全过程数字化采购管理平台。该平台具备内外协同的能力,通过待办消息、招标公告、中标公告和信息发布等功能模块…...
[python]基于faster whisper实时语音识别语音转文本
语音识别转文本相信很多人都用过,不管是手机自带,还是腾讯视频都附带有此功能,今天简单说下: faster whisper地址: https://github.com/SYSTRAN/faster-whisperhttps://link.zhihu.com/?targethttps%3A//github.com…...
2023纠结中前行? 2024继续还是放下?
喝下2023年的第一口雪碧,没有想像中的那么期待,甜水,放弃吧;还是吃些水果吧,不行吃块肉、喝两口酒~ 关于生活 挣扎了10几年的一颗牙“终于“掉了,几个月时间都在为新牙努力着;”进了医院就不在…...
原型链补充
1.什么是原型对象 函数的独有属性,他用prototype来表示,可以在函数的prototype上挂载一些公用的属性和方法,供实例化对象来访问。 2.__proto__属性 这个属性每一个对象都有,实例化对象就是通过这个属性,来访问原型对象上的属性和方法的。 3.三者之间的关系 1.在构造函数的原型…...