二叉树的中序遍历,力扣
目录
题目地址:
题目:
解题方法:
解题分析:
解题思路:
代码实现:
注:
代码实现(递归):
代码实现(迭代):
题目地址:
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;…...

微信小程序 - 手机震动
一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注:文档 https://developers.weixin.qq…...
管理学院权限管理系统开发总结
文章目录 🎓 管理学院权限管理系统开发总结 - 现代化Web应用实践之路📝 项目概述🏗️ 技术架构设计后端技术栈前端技术栈 💡 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 🗄️ 数据库设…...

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

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

嵌入式学习笔记DAY33(网络编程——TCP)
一、网络架构 C/S (client/server 客户端/服务器):由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序,负责提供用户界面和交互逻辑 ,接收用户输入,向服务器发送请求,并展示服务…...

计算机基础知识解析:从应用到架构的全面拆解
目录 前言 1、 计算机的应用领域:无处不在的数字助手 2、 计算机的进化史:从算盘到量子计算 3、计算机的分类:不止 “台式机和笔记本” 4、计算机的组件:硬件与软件的协同 4.1 硬件:五大核心部件 4.2 软件&#…...
如何通过git命令查看项目连接的仓库地址?
要通过 Git 命令查看项目连接的仓库地址,您可以使用以下几种方法: 1. 查看所有远程仓库地址 使用 git remote -v 命令,它会显示项目中配置的所有远程仓库及其对应的 URL: git remote -v输出示例: origin https://…...
FOPLP vs CoWoS
以下是 FOPLP(Fan-out panel-level packaging 扇出型面板级封装)与 CoWoS(Chip on Wafer on Substrate)两种先进封装技术的详细对比分析,涵盖技术原理、性能、成本、应用场景及市场趋势等维度: 一、技术原…...
shell脚本质数判断
shell脚本质数判断 shell输入一个正整数,判断是否为质数(素数)shell求1-100内的质数shell求给定数组输出其中的质数 shell输入一个正整数,判断是否为质数(素数) 思路: 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回溯的问题,对于这类问题大家还是要多刷和总结,总体难度还是偏大。 对于回溯问题有几个关键点: 1.首先对于这类回溯可以节点可以随机选择的问题,要做mian函数中循环调用dfs(i&#x…...