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上下级联…...

网络编程(Modbus进阶)
思维导图 Modbus RTU(先学一点理论) 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议,由 Modicon 公司(现施耐德电气)于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...

19c补丁后oracle属主变化,导致不能识别磁盘组
补丁后服务器重启,数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后,存在与用户组权限相关的问题。具体表现为,Oracle 实例的运行用户(oracle)和集…...

.Net框架,除了EF还有很多很多......
文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

376. Wiggle Subsequence
376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

NFT模式:数字资产确权与链游经济系统构建
NFT模式:数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新:构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议:基于LayerZero协议实现以太坊、Solana等公链资产互通,通过零知…...

dify打造数据可视化图表
一、概述 在日常工作和学习中,我们经常需要和数据打交道。无论是分析报告、项目展示,还是简单的数据洞察,一个清晰直观的图表,往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server,由蚂蚁集团 AntV 团队…...

Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)
引言 在人工智能飞速发展的今天,大语言模型(Large Language Models, LLMs)已成为技术领域的焦点。从智能写作到代码生成,LLM 的应用场景不断扩展,深刻改变了我们的工作和生活方式。然而,理解这些模型的内部…...
Caliper 配置文件解析:fisco-bcos.json
config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...

论文阅读笔记——Muffin: Testing Deep Learning Libraries via Neural Architecture Fuzzing
Muffin 论文 现有方法 CRADLE 和 LEMON,依赖模型推理阶段输出进行差分测试,但在训练阶段是不可行的,因为训练阶段直到最后才有固定输出,中间过程是不断变化的。API 库覆盖低,因为各个 API 都是在各种具体场景下使用。…...