当前位置: 首页 > news >正文

Hot100 - 二叉树的中序遍历

Hot100 - 二叉树的中序遍历

image-20241202235447061

image-20241202235425479

最佳思路:

  • 中序遍历的顺序是:左子树 -> 根节点 -> 右子树。为了实现这个顺序,我们可以利用栈来模拟递归过程,从而避免栈溢出的问题。
  • 在遍历过程中,始终向左子树深入,直到叶子节点为止,然后回溯并访问节点,再转向右子树。

时间复杂度:

  • 时间复杂度为 O(n),其中 n 为二叉树的节点数。每个节点都被访问一次,因此时间复杂度为线性。
  • 空间复杂度为 O(h),其中 h 是二叉树的高度。最坏情况下,栈的空间复杂度为树的高度,即树为完全不平衡时为 O(n),最优情况下为平衡二叉树时为 O(log n)。

思路解析:

  1. 使用栈模拟递归:在中序遍历中,首先访问左子树,再访问根节点,最后访问右子树。传统的递归方式非常直观,但栈的实现可以有效避免递归深度过大导致栈溢出的风险。
  2. 模拟遍历过程:我们从根节点开始,反复将当前节点及其左子树压入栈中。直到左子树为空(即叶子节点),然后开始弹出栈中的节点并访问它们,接着访问其右子树。这样可以确保中序遍历的顺序。
  3. 边界条件处理:需要在栈为空并且当前节点为空时停止遍历,确保程序不会无限循环。

代码实现:

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 - 二叉树的中序遍历 最佳思路&#xff1a; 中序遍历的顺序是&#xff1a;左子树 -> 根节点 -> 右子树。为了实现这个顺序&#xff0c;我们可以利用栈来模拟递归过程&#xff0c;从而避免栈溢出的问题。在遍历过程中&#xff0c;始终向左子树深入&#xff0c;直到…...

docker build ubuntu ssh

dockerfile 构建镜像 为了使用Dockerfile构建Docker镜像&#xff0c;请遵循以下步骤&#xff1a; 创建一个名为Dockerfile的文件&#xff0c;并在其中定义镜像的构建指令。 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优化算法的基本步骤&#xff1a;三、详细流程四、总结 二、实验结果…...

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

重试机制 当任务出现异常的时候&#xff0c;会直接停止任务——解决方式&#xff0c;重试机制 1、设置checkpoint后&#xff0c;会给任务一个重启策略——无限重启 2、可以手动设置任务的重启策略 代码设置 //开启checkpoint后&#xff0c;默认是无限重启&#xff0c;可以…...

第三方Cookie的消亡与Google服务器端标记的崛起

随着互联网用户对隐私保护的关注日益增强&#xff0c;各大浏览器正在逐步淘汰第三方Cookie。这一变革深刻影响了广告商和数字营销人员的用户跟踪和数据分析方式。然而&#xff0c;Google推出的服务器端标记技术为这一挑战提供了新的解决方案。 什么是第三方Cookie&#xff1f; …...

微信小程序——文档下载功能分享(含代码)

✅作者简介&#xff1a;2022年博客新星 第八。热爱国学的Java后端开发者&#xff0c;修心和技术同步精进。 &#x1f34e;个人主页&#xff1a;Java Fans的博客 &#x1f34a;个人信条&#xff1a;不迁怒&#xff0c;不贰过。小知识&#xff0c;大智慧。 &#x1f49e;当前专栏…...

Burp Suite 全面解析:开启你的 Web 安全测试之旅

声明&#xff01; 学习视频来自B站up主 **泷羽sec** 有兴趣的师傅可以关注一下&#xff0c;如涉及侵权马上删除文章&#xff0c;笔记只是方便各位师傅的学习和探讨&#xff0c;文章所提到的网站以及内容&#xff0c;只做学习交流&#xff0c;其他均与本人以及泷羽sec团队无关&a…...

Oracle DataGuard 主备正常切换 (Switchover)

前言 众所周知&#xff0c;DataGuard 的切换分为两种情况&#xff1a; 系统正常情况下的切换&#xff1a;这种方式称为 switchover&#xff0c;是无损切换&#xff0c;不会丢失数据。灾难情况下的切换&#xff1a;这种情况下一般主库已经启动不起来了&#xff0c;称为 failov…...

为什么编程语言会设计不可变的对象?字符串不可变?NSString *s = @“hello“变量s是不可变的吗?Rust内部可变性的意义?

为什么编程语言会设计不可变的对象? Java和C#中String是不可变的&#xff0c;StringBuilder是可变的。Obj-C中NSArray是不可变数组&#xff0c;NSMutableArray是可变数组。编程语言设计不可变的对象其实是为了优化(更高性能和节省存储空间)、安全(包括线程安全)。 字符串不可变…...

安装 RabbitMQ 服务

安装 RabbitMQ 服务 一. RabbitMQ 需要依赖 Erlang/OTP 环境 (1) 先去 RabbitMQ 官网&#xff0c;查看 RabbitMQ 需要的 Erlang 支持&#xff1a;https://www.rabbitmq.com/ 进入官网&#xff0c;在 Docs -> Install and Upgrade -> Erlang Version Requirements (2) …...

爬虫—Scrapy 整合 ChromeDriver 实现动态网页拉取

在进行爬虫开发时&#xff0c;使用 Scrapy 配合 ChromeDriver 来模拟真实浏览器加载 JavaScript 渲染内容是一种常见且高效的方法。Scrapy 本身是一个非常强大的爬虫框架&#xff0c;然而它默认使用的是 requests 库来抓取静态网页内容。对于需要通过 JavaScript 渲染的动态网页…...

Linux 进程管理详解

Linux 进程管理详解 引言 在现代操作系统中&#xff0c;进程是执行程序的基本单位。Linux作为一个强大的多任务操作系统&#xff0c;提供了丰富且灵活的机制来管理和控制进程。本文将详细介绍Linux进程管理的基本概念、核心机制以及常用的管理工具&#xff0c;帮助读者深入了…...

MySQL更新JSON字段key:value形式

MySQL更新JSON字段key:value形式 1. 介绍 ‌MySQL的JSON数据类型‌是MySQL 5.7及以上版本中引入的一种数据类型&#xff0c;用于存储JSON格式的数据。使用JSON数据类型可以自动校验文档是否满足JSON格式的要求&#xff0c;优化存储格式&#xff0c;并允许快速访问文档中的特定…...

vue.js学习(day 18)

实例&#xff1a;面经基础版...

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 容器星河与镜像灯塔&#xff1a;Linux 系统下解锁应用部署奇幻征程前言一 、docker上部署mysql1. 拉取mysql镜像2. 创建容器3. 远程登录mysql 二 、docker上部署nginx1. 拉取nginx镜像2. 在dockerTar目录下 上传nginx.tar rz命令3. 创建nginx容器4…...

不同云计算网络安全等级

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

手机实时提取SIM卡打电话的信令声音-蓝牙电话如何适配eSIM卡的手机

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

视频流媒体服务解决方案之Liveweb视频汇聚平台

一&#xff0c;Liveweb视频汇聚平台简介: LiveWeb是深圳市好游科技有限公司开发的一套综合视频汇聚管理平台&#xff0c;可提供多协议&#xff08;RTSP/RTMP/GB28181/海康Ehome/大华&#xff0c;海康SDK等&#xff09;的视频设备接入&#xff0c;支持GB/T28181上下级联&#xf…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...

Webpack性能优化:构建速度与体积优化策略

一、构建速度优化 1、​​升级Webpack和Node.js​​ ​​优化效果​​&#xff1a;Webpack 4比Webpack 3构建时间降低60%-98%。​​原因​​&#xff1a; V8引擎优化&#xff08;for of替代forEach、Map/Set替代Object&#xff09;。默认使用更快的md4哈希算法。AST直接从Loa…...

Cursor AI 账号纯净度维护与高效注册指南

Cursor AI 账号纯净度维护与高效注册指南&#xff1a;解决限制问题的实战方案 风车无限免费邮箱系统网页端使用说明|快速获取邮箱|cursor|windsurf|augment 问题背景 在成功解决 Cursor 环境配置问题后&#xff0c;许多开发者仍面临账号纯净度不足导致的限制问题。无论使用 16…...

标注工具核心架构分析——主窗口的图像显示

&#x1f3d7;️ 标注工具核心架构分析 &#x1f4cb; 系统概述 主要有两个核心类&#xff0c;采用经典的 Scene-View 架构模式&#xff1a; &#x1f3af; 核心类结构 1. AnnotationScene (QGraphicsScene子类) 主要负责标注场景的管理和交互 &#x1f527; 关键函数&…...

作为点的对象CenterNet论文阅读

摘要 检测器将图像中的物体表示为轴对齐的边界框。大多数成功的目标检测方法都会枚举几乎完整的潜在目标位置列表&#xff0c;并对每一个位置进行分类。这种做法既浪费又低效&#xff0c;并且需要额外的后处理。在本文中&#xff0c;我们采取了不同的方法。我们将物体建模为单…...

C++ Saucer 编写Windows桌面应用

文章目录 一、背景二、Saucer 简介核心特性典型应用场景 三、生成自己的项目四、以Win32项目方式构建Win32项目禁用最大化按钮 五、总结 一、背景 使用Saucer框架&#xff0c;开发Windows桌面应用&#xff0c;把一个html页面作为GUI设计放到Saucer里&#xff0c;隐藏掉运行时弹…...

vue3 手动封装城市三级联动

要做的功能 示意图是这样的&#xff0c;因为后端给的数据结构 不足以使用ant-design组件 的联动查询组件 所以只能自己分装 组件 当然 这个数据后端给的不一样的情况下 可能组件内对应的 逻辑方式就不一样 毕竟是 三个 数组 省份 城市 区域 我直接粘贴组件代码了 <temp…...

稻米分类和病害检测数据集(猫脸码客第237期)

稻米分类图像数据集&#xff1a;驱动农业智能化发展的核心资源 引言 在全球农业体系中&#xff0c;稻米作为最关键的粮食作物之一&#xff0c;其品种多样性为人类饮食提供了丰富选择。然而&#xff0c;传统稻米分类方法高度依赖人工经验&#xff0c;存在效率低、主观性强等缺…...