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

二叉树前序遍历的 Java 实现,包括递归和非递归两种方式

二叉树前序遍历是一种遍历树节点的方式,遵循特定的顺序。其基本过程可以总结为以下几个步骤:

前序遍历的顺序
访问根节点:首先处理当前节点。
递归遍历左子树:然后依次访问左子树。
递归遍历右子树:最后访问右子树。
这种遍历方式的特点是每次都会先处理根节点,再处理左右子树,因此叫做“前序”。

例子
考虑下面的二叉树:

    A/ \B   C/ \
D   E

前序遍历的步骤:

访问根节点 A
递归访问左子树:
访问 B
递归访问 B 的左子树:
访问 D
递归访问 B 的右子树:
访问 E
递归访问右子树:
访问 C
前序遍历的结果:A, B, D, E, C

特点
树的结构:前序遍历能够保存树的结构。通过前序遍历的结果,可以恢复出原来的树形结构。
适用场景:在某些场景下,例如复制树或者进行某些类型的树形操作,前序遍历是非常有效的。
递归与非递归:前序遍历可以通过递归和非递归(使用栈)两种方式实现。
时间复杂度
前序遍历的时间复杂度为 O(n),其中 n 是树中节点的总数,因为每个节点都要被访问一次。

空间复杂度
递归实现的空间复杂度为 O(h),h 是树的高度,主要由递归调用栈占用。
非递归实现的空间复杂度也是 O(h),因为栈中存储的节点数不超过树的高度。

下面是二叉树前序遍历的 Java 实现,包括递归和非递归两种方式。

  1. 递归实现
class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val = x;}
}import java.util.ArrayList;
import java.util.List;public class PreorderTraversal {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();traverse(root, result);return result;}private void traverse(TreeNode node, List<Integer> result) {if (node != null) {result.add(node.val); // 访问根节点traverse(node.left, result); // 递归左子树traverse(node.right, result); // 递归右子树}}
}

2. 非递归实现

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;public class PreorderTraversalIterative {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();if (root == null) {return result;}Stack<TreeNode> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()) {TreeNode node = stack.pop();result.add(node.val); // 访问根节点if (node.right != null) {stack.push(node.right); // 先右后左入栈}if (node.left != null) {stack.push(node.left);}}return result;}
}

示例使用
假设有如下的二叉树:

// 创建二叉树
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);// 递归遍历
PreorderTraversal pt = new PreorderTraversal();
List<Integer> result = pt.preorderTraversal(root);
System.out.println(result); // 输出: [1, 2, 4, 5, 3]// 非递归遍历
PreorderTraversalIterative pti = new PreorderTraversalIterative();
List<Integer> resultIterative = pti.preorderTraversal(root);
System.out.println(resultIterative); // 输出: [1, 2, 4, 5, 3]

相关文章:

二叉树前序遍历的 Java 实现,包括递归和非递归两种方式

二叉树前序遍历是一种遍历树节点的方式&#xff0c;遵循特定的顺序。其基本过程可以总结为以下几个步骤&#xff1a; 前序遍历的顺序 访问根节点&#xff1a;首先处理当前节点。 递归遍历左子树&#xff1a;然后依次访问左子树。 递归遍历右子树&#xff1a;最后访问右子树。 …...

QT开发:构建现代UI的利器:深入详解QML和Qt Quick基础开发技术

目录 引言 目录 1. 什么是QML和Qt Quick QML的优势 2. QML基础语法 组件 属性 JavaScript表达式 3. 数据绑定 直接绑定 双向绑定 4. 属性和属性别名 属性 属性别名 5. 信号与槽机制 定义信号 处理信号 6. 动画与过渡效果 简单动画 过渡效果 7. 构…...

vue前端使用pdfjs与pdfdist-mergeofd 实现预览pdf并翻页,同时解决预览pdf显示模糊的问题

vue前端使用pdfjs与pdfdist-mergeofd 实现预览pdf并翻页&#xff0c;同时解决预览pdf显示模糊的问题 插件介绍 pdfdist-mergeofd插件的作用可查看这篇文章&#xff0c;同时使用ofdjs和pdfjs遇到的问题&#xff0c;和解决方法——懒加载 该插件主要是为了解决pdfjs和ofdjs同时…...

C语言——回调函数

1、回调函数 在学习了函数之后&#xff0c;我发现了一个比较难的函数——回调函数 回调函数 (Callback Function) 指的是一种函数&#xff0c;它被作为参数传递给另一个函数&#xff0c;并在满足特定条件或事件发生后被调用执行。 它允许你将一段代码延迟执行&#xff0c;或者…...

2016年ATom-1飞行活动期间以10秒间隔进行的一氧化碳(CO)观测数据

目录 简介 摘要 代码 引用 网址推荐 知识星球 机器学习 ATom: Observed and GEOS-5 Simulated CO Concentrations with Tagged Tracers for ATom-1 简介 该数据集包含2016年ATom-1飞行活动期间以10秒间隔进行的一氧化碳&#xff08;CO&#xff09;观测数据&#xff0c;…...

MLM之Emu3:Emu3(仅需下一个Token预测)的简介、安装和使用方法、案例应用之详细攻略

MLM之Emu3&#xff1a;Emu3(仅需下一个Token预测)的简介、安装和使用方法、案例应用之详细攻略 导读&#xff1a;这篇论文介绍了Emu3&#xff0c;一个基于单一Transformer架构&#xff0c;仅使用下一个token预测进行训练的多模态模型。 >> 背景痛点&#xff1a; 多模态任…...

Spring Boot与Flyway实现自动化数据库版本控制

一、为什么使用Flyway 最简单的一个项目是一个软件连接到一个数据库&#xff0c;但是大多数项目中我们不仅要处理我们开发环境的副本&#xff0c;还需要处理其他很多副本。例如&#xff1a;开发环境、测试环境、生产环境。想到数据库管理&#xff0c;我们立刻就能想到一系列问…...

input角度:I2C触摸屏驱动分析和编写一个简单的I2C驱动程序

往期内容 本专栏往期内容&#xff1a; input子系统的框架和重要数据结构详解-CSDN博客input device和input handler的注册以及匹配过程解析-CSDN博客input device和input handler的注册以及匹配过程解析-CSDN博客编写一个简单的Iinput_dev框架-CSDN博客GPIO按键驱动分析与使用&…...

SQL-lab靶场less1-4

说明&#xff1a;部分内容来源于网络&#xff0c;如有侵权联系删除 前情提要&#xff1a;搭建sql-lab本地靶场的时候发现一些致命的报错&#xff1a; 这个程序只能在php 5.x上运行&#xff0c;在php 7及更高版本上&#xff0c;函数“mysql_query”和一些相关函数被删除&#xf…...

【生成模型之二】diffusion model模型

【算法简历修改、职业规划、校招实习咨询请私信联系】 【Latent-Diffusion 代码】 生成模型分类概述 Diffusion Model&#xff0c;这一深度生成模型&#xff0c;源自物理学中的扩散现象&#xff0c;呈现出令人瞩目的创新性。与传统的生成模型&#xff0c;如VAE、GAN相比&…...

记录 Maven 版本覆盖 Bug 的解决过程

背景 在使用 Maven 进行项目管理时&#xff0c;依赖版本的管理是一个常见且重要的环节。最近&#xff0c;在我的项目中遇到了一个关于依赖版本覆盖的 Bug&#xff0c;这个问题导致了 Apollo 框架的版本不一致&#xff0c;影响了项目的正常运行。以下是我解决这个问题的过程记录…...

【K8S系列】Kubernetes Service 基础知识 详细介绍

在 Kubernetes 中&#xff0c;Service 是一种抽象的资源&#xff0c;用于定义一组 Pod 的访问策略。它为这些 Pod 提供了一个稳定的访问入口&#xff0c;解决了 Pod 可能频繁变化的问题。本文将详细介绍 Kubernetes Service 的类型、功能、使用场景、DNS 和负载均衡等方面。 1.…...

python在物联网领域的数据应用分析与实战!

引言 物联网(IoT)是一个快速发展的领域,涉及到各种设备和传感器的连接与数据交换。随着设备数量的激增,数据的产生速度也在不断加快。 如何有效地分析和利用这些数据,成为了物联网应用成功的关键。Python作为一种强大的编程语言,因其简洁易用的特性和丰富的库支持,成为…...

目标跟踪算法-卡尔曼滤波详解

卡尔曼滤波是一种递归的优化算法&#xff0c;用于估计一个系统的动态状态&#xff0c;常用于跟踪、导航、时间序列分析等领域。它的关键在于使用一系列测量数据&#xff08;通常含噪声&#xff09;来估计系统的真实状态&#xff0c;使得估计值更接近实际情况。卡尔曼滤波器适合…...

SpringBoot后端开发常用工具详细介绍——application多环境配置与切换

文章目录 引言介绍application.yml&#xff08;主配置文件&#xff09;application-dev.yml&#xff08;开发环境配置&#xff09;application-test.yml&#xff08;测试环境配置&#xff09;application-prod.yml&#xff08;生产环境配置&#xff09;激活配置文件参考内容 引…...

php反序列化漏洞典型例题

1.靶场环境 ctfhub-技能树-pklovecloud 引用题目&#xff1a; 2021-第五空间智能安全大赛-Web-pklovecloud 2.过程 2.1源代码 启动靶场环境&#xff0c;访问靶场环境&#xff0c;显示源码&#xff1a;直接贴在下面&#xff1a; <?php include flag.php; class pks…...

浅析Android View绘制过程中的Surface

前言 在《浅析Android中View的测量布局流程》中我们对VSYNC信号到达App进程之后开启的View布局过程进行了分析&#xff0c;经过对整个App界面的View树进行遍历完成了测量和布局&#xff0c;确定了View的大小以及在屏幕中所处的位置。但是&#xff0c;如果想让用户在屏幕上看到…...

基于卷积神经网络的大豆种子缺陷识别系统,resnet50,mobilenet模型【pytorch框架+python源码】

更多目标检测和图像分类识别项目可看我主页其他文章 功能演示&#xff1a; 大豆种子缺陷识别系统&#xff0c;卷积神经网络&#xff0c;resnet50&#xff0c;mobilenet【pytorch框架&#xff0c;python源码】_哔哩哔哩_bilibili &#xff08;一&#xff09;简介 基于卷积神…...

HarmonyOS项目开发一多简介

目录 一、布局能力概述 二、自适应布局 三、响应式布局 四、典型布局场景 一、布局能力概述 布局决定页面元素排布及显示&#xff1a;在页面设计及开发中&#xff0c;布局能力至关重要&#xff0c;主要通过组件结构来确定使用何种布局。 自适应布局与响应式布局&#xff1…...

C++基础三

构造函数 构造函数(初始化类成员变量)&#xff1a; 1、属于类的成员函数之一 2、构造函数没有返回类型 3、构造函数的函数名必须与类名相同 4、构造函数不允许手动调用(不能通过类对象调用) 5、构造函数在类对象创建时会被自动调用 6、如果没有显示声…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

vue3 字体颜色设置的多种方式

在Vue 3中设置字体颜色可以通过多种方式实现&#xff0c;这取决于你是想在组件内部直接设置&#xff0c;还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法&#xff1a; 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...

人机融合智能 | “人智交互”跨学科新领域

本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...

【JVM】Java虚拟机(二)——垃圾回收

目录 一、如何判断对象可以回收 &#xff08;一&#xff09;引用计数法 &#xff08;二&#xff09;可达性分析算法 二、垃圾回收算法 &#xff08;一&#xff09;标记清除 &#xff08;二&#xff09;标记整理 &#xff08;三&#xff09;复制 &#xff08;四&#xff…...

C++ 设计模式 《小明的奶茶加料风波》

&#x1f468;‍&#x1f393; 模式名称&#xff1a;装饰器模式&#xff08;Decorator Pattern&#xff09; &#x1f466; 小明最近上线了校园奶茶配送功能&#xff0c;业务火爆&#xff0c;大家都在加料&#xff1a; 有的同学要加波霸 &#x1f7e4;&#xff0c;有的要加椰果…...

4. TypeScript 类型推断与类型组合

一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式&#xff0c;自动确定它们的类型。 这一特性减少了显式类型注解的需要&#xff0c;在保持类型安全的同时简化了代码。通过分析上下文和初始值&#xff0c;TypeSc…...