Hot100 - 二叉树的中序遍历
Hot100 - 二叉树的中序遍历
最佳思路:
- 中序遍历的顺序是:左子树 -> 根节点 -> 右子树。为了实现这个顺序,我们可以利用栈来模拟递归过程,从而避免栈溢出的问题。
- 在遍历过程中,始终向左子树深入,直到叶子节点为止,然后回溯并访问节点,再转向右子树。
时间复杂度:
- 时间复杂度为 O(n),其中 n 为二叉树的节点数。每个节点都被访问一次,因此时间复杂度为线性。
- 空间复杂度为 O(h),其中 h 是二叉树的高度。最坏情况下,栈的空间复杂度为树的高度,即树为完全不平衡时为 O(n),最优情况下为平衡二叉树时为 O(log n)。
思路解析:
- 使用栈模拟递归:在中序遍历中,首先访问左子树,再访问根节点,最后访问右子树。传统的递归方式非常直观,但栈的实现可以有效避免递归深度过大导致栈溢出的风险。
- 模拟遍历过程:我们从根节点开始,反复将当前节点及其左子树压入栈中。直到左子树为空(即叶子节点),然后开始弹出栈中的节点并访问它们,接着访问其右子树。这样可以确保中序遍历的顺序。
- 边界条件处理:需要在栈为空并且当前节点为空时停止遍历,确保程序不会无限循环。
代码实现:
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();// 继续遍历直到栈为空且节点为 nullwhile (stack.size() > 0 || root != null) {// 深入左子树if (root != null) {stack.add(root);root = root.left; // 遍历到左子树的最深节点} else {// 弹出栈顶元素,访问节点TreeNode tmp = stack.pop();res.add(tmp.val);// 转向右子树root = tmp.right;}}return res;}
}
思路总结:
- 本题的关键在于如何通过栈模拟递归来实现中序遍历。通过控制栈的操作,我们能够按顺序遍历每一个节点,避免递归的深度问题。相较于传统递归,迭代的栈方式在某些场景下能更好地控制空间复杂度,尤其是在树结构较大时。
相关文章:

Hot100 - 二叉树的中序遍历
Hot100 - 二叉树的中序遍历 最佳思路: 中序遍历的顺序是:左子树 -> 根节点 -> 右子树。为了实现这个顺序,我们可以利用栈来模拟递归过程,从而避免栈溢出的问题。在遍历过程中,始终向左子树深入,直到…...
docker build ubuntu ssh
dockerfile 构建镜像 为了使用Dockerfile构建Docker镜像,请遵循以下步骤: 创建一个名为Dockerfile的文件,并在其中定义镜像的构建指令。 FROM swr.cn-north-4.myhuaweicloud.com/ddn-k8s/docker.io/ubuntu:24.04# 安装openssh-server和pas…...

三维路径规划|基于黑翅鸢BKA优化算法的三维路径规划Matlab程序
三维路径规划|基于黑翅鸢BKA优化算法的三维路径规划Matlab程序 文章目录 前言三维路径规划|基于黑翅鸢BKA优化算法的三维路径规划Matlab程序基于黑翅鸢BKA优化算法的三维路径规划一、研究基本原理二、黑翅鸢BKA优化算法的基本步骤:三、详细流程四、总结 二、实验结果…...

day01(Linux底层)基础知识
目录 导学 基础知识 1、Bootloader是什么 2、Bootloader的基本作用 3、入式中常见的Bootloader有哪些 4、Linux系统移植为什么要使用bootloader 5、uboot和Bootloader之间的关系 6.Uboot的获取 7、uboot版本命名 8、uboot版本选择 9、uboot的特点 10.Uboot使用 导学…...
flink学习(13)—— 重试机制和维表join
重试机制 当任务出现异常的时候,会直接停止任务——解决方式,重试机制 1、设置checkpoint后,会给任务一个重启策略——无限重启 2、可以手动设置任务的重启策略 代码设置 //开启checkpoint后,默认是无限重启,可以…...
第三方Cookie的消亡与Google服务器端标记的崛起
随着互联网用户对隐私保护的关注日益增强,各大浏览器正在逐步淘汰第三方Cookie。这一变革深刻影响了广告商和数字营销人员的用户跟踪和数据分析方式。然而,Google推出的服务器端标记技术为这一挑战提供了新的解决方案。 什么是第三方Cookie? …...

微信小程序——文档下载功能分享(含代码)
✅作者简介:2022年博客新星 第八。热爱国学的Java后端开发者,修心和技术同步精进。 🍎个人主页:Java Fans的博客 🍊个人信条:不迁怒,不贰过。小知识,大智慧。 💞当前专栏…...
Burp Suite 全面解析:开启你的 Web 安全测试之旅
声明! 学习视频来自B站up主 **泷羽sec** 有兴趣的师傅可以关注一下,如涉及侵权马上删除文章,笔记只是方便各位师傅的学习和探讨,文章所提到的网站以及内容,只做学习交流,其他均与本人以及泷羽sec团队无关&a…...
Oracle DataGuard 主备正常切换 (Switchover)
前言 众所周知,DataGuard 的切换分为两种情况: 系统正常情况下的切换:这种方式称为 switchover,是无损切换,不会丢失数据。灾难情况下的切换:这种情况下一般主库已经启动不起来了,称为 failov…...
为什么编程语言会设计不可变的对象?字符串不可变?NSString *s = @“hello“变量s是不可变的吗?Rust内部可变性的意义?
为什么编程语言会设计不可变的对象? Java和C#中String是不可变的,StringBuilder是可变的。Obj-C中NSArray是不可变数组,NSMutableArray是可变数组。编程语言设计不可变的对象其实是为了优化(更高性能和节省存储空间)、安全(包括线程安全)。 字符串不可变…...

安装 RabbitMQ 服务
安装 RabbitMQ 服务 一. RabbitMQ 需要依赖 Erlang/OTP 环境 (1) 先去 RabbitMQ 官网,查看 RabbitMQ 需要的 Erlang 支持:https://www.rabbitmq.com/ 进入官网,在 Docs -> Install and Upgrade -> Erlang Version Requirements (2) …...
爬虫—Scrapy 整合 ChromeDriver 实现动态网页拉取
在进行爬虫开发时,使用 Scrapy 配合 ChromeDriver 来模拟真实浏览器加载 JavaScript 渲染内容是一种常见且高效的方法。Scrapy 本身是一个非常强大的爬虫框架,然而它默认使用的是 requests 库来抓取静态网页内容。对于需要通过 JavaScript 渲染的动态网页…...
Linux 进程管理详解
Linux 进程管理详解 引言 在现代操作系统中,进程是执行程序的基本单位。Linux作为一个强大的多任务操作系统,提供了丰富且灵活的机制来管理和控制进程。本文将详细介绍Linux进程管理的基本概念、核心机制以及常用的管理工具,帮助读者深入了…...
MySQL更新JSON字段key:value形式
MySQL更新JSON字段key:value形式 1. 介绍 MySQL的JSON数据类型是MySQL 5.7及以上版本中引入的一种数据类型,用于存储JSON格式的数据。使用JSON数据类型可以自动校验文档是否满足JSON格式的要求,优化存储格式,并允许快速访问文档中的特定…...

vue.js学习(day 18)
实例:面经基础版...
WINDOWS 单链表SLIST_ENTRY使用
1.初始化链表头 //初始化链表头qq1490900437 void InitialGloubleVar() {while (1){G_Handle.SaveProcessThreadHandle (PSLIST_HEADER)_aligned_malloc(sizeof(SLIST_HEADER), MEMORY_ALLOCATION_ALIGNMENT);if (G_Handle.SaveProcessThreadHandle ! NULL){break;}}Initiali…...

【Linux 篇】Docker 容器星河与镜像灯塔:Linux 系统下解锁应用部署奇幻征程
文章目录 【Linux 篇】Docker 容器星河与镜像灯塔:Linux 系统下解锁应用部署奇幻征程前言一 、docker上部署mysql1. 拉取mysql镜像2. 创建容器3. 远程登录mysql 二 、docker上部署nginx1. 拉取nginx镜像2. 在dockerTar目录下 上传nginx.tar rz命令3. 创建nginx容器4…...

不同云计算网络安全等级
导读云计算的本质是服务,如果不能将计算资源规模化/大范围的进行共享,如果不能真正以服务的形式提供,就根本算不上云计算。 等级保护定级流程 定级是开展网络安全等级保护工作的 “基本出发点”,虚拟化技术使得传统的网络边界变…...

手机实时提取SIM卡打电话的信令声音-蓝牙电话如何适配eSIM卡的手机
手机实时提取SIM卡打电话的信令声音 --蓝牙电话如何适配eSIM卡的手机 一、前言 蓝牙电话的海外战略中,由于海外智能手机市场中政策的差异性,对内置eSIM卡的手机进行支持是非常合理的需求。Android系列手机中,无论是更换通信运营商…...

视频流媒体服务解决方案之Liveweb视频汇聚平台
一,Liveweb视频汇聚平台简介: LiveWeb是深圳市好游科技有限公司开发的一套综合视频汇聚管理平台,可提供多协议(RTSP/RTMP/GB28181/海康Ehome/大华,海康SDK等)的视频设备接入,支持GB/T28181上下级联…...
STM32+rt-thread判断是否联网
一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...
c++ 面试题(1)-----深度优先搜索(DFS)实现
操作系统:ubuntu22.04 IDE:Visual Studio Code 编程语言:C11 题目描述 地上有一个 m 行 n 列的方格,从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子,但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...
渲染学进阶内容——模型
最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

Keil 中设置 STM32 Flash 和 RAM 地址详解
文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案
随着新能源汽车的快速普及,充电桩作为核心配套设施,其安全性与可靠性备受关注。然而,在高温、高负荷运行环境下,充电桩的散热问题与消防安全隐患日益凸显,成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

Android15默认授权浮窗权限
我们经常有那种需求,客户需要定制的apk集成在ROM中,并且默认授予其【显示在其他应用的上层】权限,也就是我们常说的浮窗权限,那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...

IT供电系统绝缘监测及故障定位解决方案
随着新能源的快速发展,光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域,IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选,但在长期运行中,例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 在 GPU 上对图像执行 均值漂移滤波(Mean Shift Filtering),用于图像分割或平滑处理。 该函数将输入图像中的…...

安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)
船舶制造装配管理现状:装配工作依赖人工经验,装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书,但在实际执行中,工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...
【Android】Android 开发 ADB 常用指令
查看当前连接的设备 adb devices 连接设备 adb connect 设备IP 断开已连接的设备 adb disconnect 设备IP 安装应用 adb install 安装包的路径 卸载应用 adb uninstall 应用包名 查看已安装的应用包名 adb shell pm list packages 查看已安装的第三方应用包名 adb shell pm list…...