当前位置: 首页 > 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…...

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

多种风格导航菜单 HTML 实现(附源码)

下面我将为您展示 6 种不同风格的导航菜单实现&#xff0c;每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

selenium学习实战【Python爬虫】

selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...

重启Eureka集群中的节点,对已经注册的服务有什么影响

先看答案&#xff0c;如果正确地操作&#xff0c;重启Eureka集群中的节点&#xff0c;对已经注册的服务影响非常小&#xff0c;甚至可以做到无感知。 但如果操作不当&#xff0c;可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...