【二叉树】Leetcode 94. 二叉树的中序遍历【简单】
二叉树的中序遍历
给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。
示例 1:

输入:root = [1,null,2,3]
输出:[1,3,2]
解题思路
中序遍历是一种二叉树遍历方式,按照“左根右”的顺序遍历二叉树节点。
- 1、递归地遍历左子树。
- 2、访问当前节点。
- 3、递归地遍历右子树。
对应先序遍历 根左右
对应后序遍历 左右根
先、中、后序遍历其实指的是遍历根节点的先后顺序
Java实现中序遍历
public class InorderTraversal {static class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int val) {this.val = val;}}public List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();inorderTraversalHelper(root, result);return result;}private void inorderTraversalHelper(TreeNode node, List<Integer> result) {if (node == null) {return;}inorderTraversalHelper(node.left, result);result.add(node.val);inorderTraversalHelper(node.right, result);}public static void main(String[] args) {// 示例用法TreeNode root = new TreeNode(1);root.left = new TreeNode(4);root.right = new TreeNode(2);root.right.left = new TreeNode(3);InorderTraversal solution = new InorderTraversal();List<Integer> result = solution.inorderTraversal(root);System.out.println(result); // 输出:[4, 1, 3, 2]}
}
Java实现先序遍历
/*** 先序遍历* 根->左->右*/
public class PreorderTraversal {static class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int val) {this.val = val;}}public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();preorderTraversalHelper(root, result);return result;}private void preorderTraversalHelper(TreeNode node, List<Integer> result) {if (node == null) {return;}result.add(node.val);preorderTraversalHelper(node.left,result);preorderTraversalHelper(node.right,result);}public static void main(String[] args) {// 示例用法TreeNode root = new TreeNode(1);root.left = new TreeNode(4);root.left.left = new TreeNode(5);root.left.left.right = new TreeNode(8);root.left.right = new TreeNode(6);root.right = new TreeNode(2);root.right.left = new TreeNode(3);PreorderTraversal solution = new PreorderTraversal();List<Integer> result = solution.preorderTraversal(root);System.out.println(result); // 输出:[1, 3, 2]}
}
Java实现后序遍历
/*** 后序遍历* 左->右->根*/
public class PostorderTraversal {static class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int val) {this.val = val;}}public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();postorderTraversalHelper(root, result);return result;}private void postorderTraversalHelper(TreeNode node, List<Integer> result) {if (node == null) {return;}postorderTraversalHelper(node.left, result);postorderTraversalHelper(node.right, result);result.add(node.val);}public static void main(String[] args) {// 示例用法TreeNode root = new TreeNode(1);root.left = new TreeNode(4);root.right = new TreeNode(2);root.right.left = new TreeNode(3);PostorderTraversal solution = new PostorderTraversal();List<Integer> result = solution.postorderTraversal(root);System.out.println(result); // 输出:[1, 3, 2]}
}
时间空间复杂度
- 时间复杂度:O(n),其中n是二叉树中的节点数,每个节点都需要访问一次。
- 空间复杂度:O(n),取决于递归调用栈的深度,最坏情况下为O(n)。
相关文章:
【二叉树】Leetcode 94. 二叉树的中序遍历【简单】
二叉树的中序遍历 给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。 示例 1: 输入:root [1,null,2,3] 输出:[1,3,2] 解题思路 中序遍历是一种二叉树遍历方式,按照“左根右”的顺序遍历二叉树节点。 1、递归…...
Linux进程控制(等待)
进程等待 为什么要进行进程等待 进程等待是什么? 怎么进行进程等待? 回到我们之前进程状态的代码, 我们知道, 在这段代码中,父进程对子进程没有做任何的操作, 所以当子进程在退出后, 会一直处于…...
结构体-C语言
目录 前言 一、定义结构 结构体变量的创建和初始化 二、结构的特殊声明 特别注意: 结构的⾃引⽤ 三、结构体内存对⻬ 对⻬规则 优化结构体 #pragma 结构体传参 四、结构体实现位段 位段的内存分配 位段的跨平台问题 前言 C 数组允许定义可存储相同类…...
Unity DOTS中的baking(四)blob assets
Unity DOTS中的baking(四)blob assets blob assets表示不可变的二进制数据,在运行时也不会发生更改。由于blob assets是只读的,这意味着可以安全地并行访问它们。此外,blob assets仅限于使用非托管类型,这意…...
第三十天-Flask模板 Jinja2
目录 1.什么是模板 2.模板引擎Jinja2 默认配置 全局对象 全局函数 上下文处理器 3.模板中变量的使用 4.模板标签 条件判断if else for循环 添加注释 设置变量 转义显示 5.过滤器 过滤器使用 自定义过滤器 6.全局函数 7.模板中的宏 模板的基础 包含语法 8.…...
在项目中数据库如何优化?【MySQL主从复制(创建一个从节点复制备份数据)】【数据库读写分离ShardingJDBC(主库写,从库读)】
MySQL主从复制 MySQL主从复制介绍MySQL复制过程分成三步:1). MySQL master 将数据变更写入二进制日志( binary log)2). slave将master的binary log拷贝到它的中继日志(relay log)3). slave重做中继日志中的事件,将数据变更反映它自…...
Fragment 与 ViewPager的联合应用(2)
5.创建底部布局bottom_layout <LinearLayout xmlns:android"http://schemas.android.com/apk/res/android"android:orientation"horizontal"android:layout_width"match_parent"android:layout_height"55dp"android:background&qu…...
OriginBot智能机器人开源套件
详情可参见:OriginBot智能机器人开源套件——支持ROS2/TogetherROS,算力强劲,配套古月居定制课程 (guyuehome.com) OriginBot智能机器人开源套件 最新消息:OriginBot V2.1.0版本正式发布,新增车牌识别,点击…...
Java Web-Maven
Maven是apache旗下的一个开源项目,是一款用于管理和构建java项目的工具 Maven的作用 1.依赖管理:方便快捷的管理项目依赖资源(jar包),避免版本冲突问题 我们有的项目需要大量的jar包,采用手动导包的方式非常繁琐,并且版本升级也…...
.Net 异步委托
委托的 BeginInvoke 方法和 EndInvoke 方法可以实现异步执行委托方法。这允许委托的方法在后台线程中执行,而不会阻塞当前线程。小编在之前的webform开发中遇到下载进度条卡死的问题就是用它解决的。 案例: namespace ConsoleApplication1 {class Progr…...
web前端面试题---->HTML、CSS
一.居中方法 block元素如何居中 margin:0 auto;position: absolute; top: 50%; left: 50%; transform: translate(-50%, -50%);flex布局: 对父元素操作 : justify-content:center; al…...
移动端Web笔记day03
移动 Web 第三题 01-移动 Web 基础 谷歌模拟器 模拟移动设备,方便查看页面效果,移动端的效果是当手机屏幕发生了变化,页面和页面中的元素也要跟着等比例变化。 屏幕分辨率 分类: 硬件分辨路 -> 物理分辨率:硬件…...
c++的学习之路:3、入门(2)
一、引用 1、引用的概念 引用不是新定义一个变量,而是给已存在变量取了一个别名,编译器不会为引用变量开辟内存空 间,它和它引用的变量共用同一块内存空间。 怎么说呢,简单点理解就是你的小名,家里人叫你小名&#…...
面试经典150题【91-100】
文章目录 面试经典150题【91-100】70.爬楼梯198.打家劫舍139.单词拆分322.零钱兑换300.递增最长子序列77.组合46.全排列39.组合总和(※)22.括号生成79.单词搜索 面试经典150题【91-100】 五道一维dp题五道回溯题。 70.爬楼梯 从递归到动态规划 public …...
在 nginx 中使用 JavaScript
前些日子尝试了在 nginx 中写 JavaScript 的效果。考虑到 JavaScript 作为编程语言不是强需求,在nginx生态上还是 lua 独大,并且还有 openresty 这样一直强力输血,大部分应用场景都能找到参考的解决方案。 插件生态来说,github 上…...
【pytorch】安装合集
使用conda或者pip安装的指令 https://pytorch.org/get-started/previous-versions/ 测试pytorch_gpu是否可用的代码 # 测试pytorch是否安装成功 import torch print(torch.__version__) print(torch.cuda.is_available())...
【教程】PLSQL查看表属性乱码解决方法
一、前言 PL/SQL是Oracle数据库的编程语言,用于编写存储过程、触发器、函数等。 今天用plsql想查看表的属性,看看各个字段的注释,可是打开一看,居然是乱码的,如下面这样 如果在使用PL/SQL查看表属性时出现乱码&…...
新书速览|Django 5企业级Web应用开发实战:视频教学版
掌握Django框架开发技能,实战投票应用系统和内容管理系统 本书内容 《Django 5企业级Web应用开发实战:视频教学版》精选当前简单、实用和流行的Django实例代码,帮助读者学习和掌握Django 5框架及其相关技术栈的开发知识。本书系统全面、内容…...
excel创建和部分使用
一.excel导出是在开发中经常操作的内容,对于excel的导出也是有各种成熟的api组件 这里是最近的项目有通过ts处理,这里的内容通过ts ①引入const XlsxPopulate require("xlsx-populate"); const XLSXChart require("xlsx-chart"); 通过命令行操作, pnp…...
pycharm使用远程服务器的jupyter环境
1、确保服务器上安装了jupyter,如果没有,执行下面命令安装 pip install jupyter2、启动jupyter notebook服务 jupyter notebook --no-browser --port8888 --ip0.0.0.0 --allow-root表明在服务器的8888 端口上启动 Jupyter Notebook,并允许从任何 IP 地…...
脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)
一、数据处理与分析实战 (一)实时滤波与参数调整 基础滤波操作 60Hz 工频滤波:勾选界面右侧 “60Hz” 复选框,可有效抑制电网干扰(适用于北美地区,欧洲用户可调整为 50Hz)。 平滑处理&…...
【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器
——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的一体化测试平台,覆盖应用全生命周期测试需求,主要提供五大核心能力: 测试类型检测目标关键指标功能体验基…...
令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍
文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结: 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析: 实际业务去理解体会统一注…...
dify打造数据可视化图表
一、概述 在日常工作和学习中,我们经常需要和数据打交道。无论是分析报告、项目展示,还是简单的数据洞察,一个清晰直观的图表,往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server,由蚂蚁集团 AntV 团队…...
短视频矩阵系统文案创作功能开发实践,定制化开发
在短视频行业迅猛发展的当下,企业和个人创作者为了扩大影响力、提升传播效果,纷纷采用短视频矩阵运营策略,同时管理多个平台、多个账号的内容发布。然而,频繁的文案创作需求让运营者疲于应对,如何高效产出高质量文案成…...
音视频——I2S 协议详解
I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议,专门用于在数字音频设备之间传输数字音频数据。它由飞利浦(Philips)公司开发,以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...
AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别
【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而,传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案,能够实现大范围覆盖并远程采集数据。尽管具备这些优势…...
c++第七天 继承与派生2
这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分:派生类构造函数与析构函数 当创建一个派生类对象时,基类成员是如何初始化的? 1.当派生类对象创建的时候,基类成员的初始化顺序 …...
深入理解Optional:处理空指针异常
1. 使用Optional处理可能为空的集合 在Java开发中,集合判空是一个常见但容易出错的场景。传统方式虽然可行,但存在一些潜在问题: // 传统判空方式 if (!CollectionUtils.isEmpty(userInfoList)) {for (UserInfo userInfo : userInfoList) {…...
用递归算法解锁「子集」问题 —— LeetCode 78题解析
文章目录 一、题目介绍二、递归思路详解:从决策树开始理解三、解法一:二叉决策树 DFS四、解法二:组合式回溯写法(推荐)五、解法对比 递归算法是编程中一种非常强大且常见的思想,它能够优雅地解决很多复杂的…...
