java实现二叉树的前序、中序、后序遍历(递归和非递归方式)以及层级遍历
java实现二叉树的前序、中序、后序遍历以及层级遍历
- 一、二叉树节点定义
- 二、递归方式
- 1.前序遍历
- 2.中序遍历
- 3.后序遍历
- 三、非递归方式
- 1.前序遍历
- 2.中序遍历
- 3.后序遍历
- 4.层级遍历
- 5.分层打印
- 四、测试用例
一、二叉树节点定义
class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val = x;}
}
二、递归方式
1.前序遍历
前序遍历(根-左-右)
public void preorderRecursive(TreeNode root) {if (root == null) {return;}// 访问根节点System.out.print(root.val + " ");// 递归遍历左子树preorderRecursive(root.left);// 递归遍历右子树preorderRecursive(root.right);
}
2.中序遍历
中序遍历(左-根-右)
public void inorderRecursive(TreeNode root) {if (root == null) {return;}// 递归遍历左子树inorderRecursive(root.left);// 访问根节点System.out.print(root.val + " ");// 递归遍历右子树inorderRecursive(root.right);
}
3.后序遍历
后序遍历(左-右-根)
public void postorderRecursive(TreeNode root) {if (root == null) {return;}// 递归遍历左子树postorderRecursive(root.left);// 递归遍历右子树postorderRecursive(root.right);// 访问根节点System.out.print(root.val + " ");
}
三、非递归方式
1.前序遍历
前序遍历(根-左-右)
public void preorderIterative(TreeNode root) {if (root == null) {return;}Stack<TreeNode> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()) {TreeNode node = stack.pop();System.out.print(node.val + " ");// 先压入右节点,再压入左节点,保证左节点先出栈if (node.right != null) {stack.push(node.right);}if (node.left != null) {stack.push(node.left);}}
}
2.中序遍历
中序遍历(左-根-右)
public void inorderIterative(TreeNode root) {Stack<TreeNode> stack = new Stack<>();TreeNode curr = root;while (curr != null || !stack.isEmpty()) {// 一直向左走,把所有左节点压栈while (curr != null) {stack.push(curr);curr = curr.left;}curr = stack.pop();System.out.print(curr.val + " ");// 转向右子树curr = curr.right;}
}
3.后序遍历
后序遍历(左-右-根)
public void postorderIterative(TreeNode root) {if (root == null) {return;}Stack<TreeNode> stack = new Stack<>();// 用于反转顺序Stack<Integer> output = new Stack<>();stack.push(root);while (!stack.isEmpty()) {TreeNode node = stack.pop();output.push(node.val);// 注意这里先左后右,这样输出栈的顺序就是右-左-根// 反转后就是左-右-根if (node.left != null) {stack.push(node.left);}if (node.right != null) {stack.push(node.right);}}// 输出结果while (!output.isEmpty()) {System.out.print(output.pop() + " ");}
}
4.层级遍历
层级遍历(Level Order Traversal)也称为广度优先遍历(BFS),是按层次从上到下、从左到右访问二叉树节点的遍历方式。
public void levelOrderTraversal(TreeNode root) {if (root == null) {return;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {TreeNode node = queue.poll();System.out.print(node.val + " ");if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}
}
5.分层打印
分层打印的实现(按层次输出)
public void levelOrderWithLevels(TreeNode root) {if (root == null) {return;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);int levelCount = 0;while (!queue.isEmpty()) {int levelSize = queue.size();System.out.print("Level " + (levelCount++) + ": ");for (int i = 0; i < levelSize; i++) {TreeNode node = queue.poll();System.out.print(node.val + " ");if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}System.out.println();}
}
四、测试用例
public static void main(String[] args) {// 构建二叉树// 1// / \// 2 3// / \// 4 5TreeNode 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);BinaryTreeTraversal traversal = new BinaryTreeTraversal();System.out.println("递归前序遍历:");traversal.preorderRecursive(root);System.out.println("\n非递归前序遍历:");traversal.preorderIterative(root);System.out.println("\n\n递归中序遍历:");traversal.inorderRecursive(root);System.out.println("\n非递归中序遍历:");traversal.inorderIterative(root);System.out.println("\n\n递归后序遍历:");traversal.postorderRecursive(root);System.out.println("\n非递归后序遍历:");traversal.postorderIterative(root);System.out.println("\n基本层级遍历:");traversal.levelOrderTraversal(root);System.out.println("\n\n分层打印层级遍历:");traversal.levelOrderWithLevels(root);
}
打印结果
相关文章:
java实现二叉树的前序、中序、后序遍历(递归和非递归方式)以及层级遍历
java实现二叉树的前序、中序、后序遍历以及层级遍历 一、二叉树节点定义二、递归方式1.前序遍历2.中序遍历3.后序遍历 三、非递归方式1.前序遍历2.中序遍历3.后序遍历4.层级遍历5.分层打印 四、测试用例 一、二叉树节点定义 class TreeNode {int val;TreeNode left;TreeNode r…...
学习笔记十三—— 理解 Rust 闭包:从语法到 impl Fn vs Box<dyn Fn>
🧠 理解 Rust 闭包:从语法到 impl Fn vs Box 📚 目录 闭包是什么?和普通函数有什么不同?闭包的语法长什么样?闭包“捕获变量”是什么意思?闭包和所有权的关系Fn、FnMut、FnOnce 三种闭包类型的…...
Linux虚拟机filezilla总是连不上
刚好有两个虚拟机,测试了一下问题所在 从第一个到第二个需要设置什么 image PNG 68.59KB image PNG 134.39KB ChatGLM 从第一个到第二个需要设置开启ssh服务,具体步骤如下: 输入以下命令来启动SSH服务: bash 复制 sud…...
NO.94十六届蓝桥杯备战|图论基础-单源最短路|常规dijkstra|堆优化dijkstra|bellman-ford|spfa(C++)
在图G中,假设 v i v_{i} vi和 v j v_{j} vj为图中的两个顶点,那么 v i v_{i} vi到 v j v_{j} vj路径上所经过边的权值之和就称为带权路径⻓度。 由于 v i v_{i} vi到 v j v_{j} vj的路径可能有多条,将带权路径⻓度最短的那条路径…...
DISCO:利用大型语言模型提取反事实
DISCO: Distilling Counterfactuals with Large Language Models - ACL Anthologyhttps://aclanthology.org/2023.acl-long.302/ 1. 概述 尽管在自然语言处理(NLP)领域针对各种推理任务取得了巨大进展(Wang 等, 2018, 2019a;Xu 等, 2020),但数据集偏差仍然是构建鲁棒模型…...
若依微服务版启动小程序后端
目录标题 本地启动,dev对应 nacos里的 xxx-xxx-dev配置文件 本地启动,dev对应 nacos里的 xxx-xxx-dev配置文件...
C语言 - 深拷贝与浅拷贝详解
深拷贝与浅拷贝详解 在 C 语言编程中,处理指针和动态内存是常见任务。在涉及数据拷贝操作时,我们经常会听到“深拷贝”和“浅拷贝”这两个术语。理解它们之间的区别对于避免程序中的内存错误和数据覆盖问题至关重要。 本文将全面讲解 C 语言中的深拷贝与…...
Serverless集群搭建:Knative
文章目录 Knative搭建1.准备工作安装Kubernetes安装 Istio 2.部署Knative Knative搭建 搭建流程图: 1.准备工作 准备工作 ● 本安装操作中的步骤 bash 适用于 MacOS 或 Linux 环境。对于 Windows,某些命令可能需要调整。 ● 本安装操作假定您具有现有…...
今日行情明日机会——20250416
指数在区间震荡,还需要等突破下跌趋势企稳 2025年4月16日涨停的主要行业方向分析 1. 外贸(9家涨停) 细分领域:跨境物流、纺织出口、供应链服务。代表个股: 五板:泰慕士(纺织服装出口龙头&…...
STM32基础教程——DMA
目录 前言 编辑 技术实现 接线图 代码实现 技术要点 DMA时钟 DMA初始化 DMA数据传输设置 数据改变与显示 实验结果 问题记录 前言 DMA(Direct Memory Access)直接存储器存取,用来提供在外设和存储器 之间或者存储器和存储器之间的高速数据传输。无需…...
Node.js 中文件系统模块(`fs`)的详细总结,包括定义、作用、各种写入方式及使用场景
Node.js 中文件系统模块(fs)的详细总结,包括定义、作用、各种写入方式及使用场景: 🧩 一、fs 模块简介 ✅ 定义 fs(File System)是 Node.js 官方内置模块,用于实现对文件和目录的操…...
MyBatis与MyBatis-Plus:字段自动填充的两种实现方式
目录 1. 使用 MyBatis 拦截器实现字段自动填充 2. 使用 MyBatis-Plus 实现字段自动填充 1. 使用 MyBatis 拦截器实现字段自动填充 实现步骤 创建拦截器 实现 MyBatis 的 Interceptor 接口,通过拦截 MyBatis 执行的 SQL 操作来自动填充公共字段 Intercepts({Signa…...
比特率、码元速率(波特率)的定义、关系及相关计算公式
一、相关定义 (一)比特率 比特率(Bit Rate):单位时间内传输的二进制比特数,是信息传输速率的度量。单位:比特每秒(bit/s,bps)。公式:比特率 传…...
炫云平台全面支持Blender4.4云渲染
随着世界渲染大赛众多优秀作品被大家关注,Blender作为建模渲染一体化的软件,也是众多3D艺术家最常用的软件之一。云渲染自然是提升创作效率必不可少的工作。这篇文章说一下炫云云渲染平台近期对Blender云渲染支持的情况。 首先,炫云客户端已经…...
Python自学第1天:变量,打印,类型转化
突然想学Python了。经过Deepseek的推荐,下载了一个Python3.12安装。安装过程请自行搜索。 乖乖从最基础的学起来,废话不说了,上链接,呃,打错了,上知识点。 变量的定义 # 定义一个整数类型的变量 age 10#…...
Flutter 从零到一
iOS 调试与开发工具指南 真机调试 Xcode run 在控制台获取 Dart VM service URIVSCode 点击 Cmd Shift P 选择 Debug: Attach to Flutter on Device粘贴 the URI 后点击 Enter 对于iOS开发者来说,使用appuploader这样的iOS开发助手可以简化真机调试的准备工作。…...
ocr-身份证正反面识别
在阿里云官网,申请一个token [阿里官方]身份证OCR文字识别_API专区_云市场-阿里云 (aliyun.com) 观察一下post请求body部分json字符串,我们根据这个创建一个java对象 先默认是人像面 public class IdentityBody {public String image;class configure…...
深入解析Spring Boot核心组件及其关键功能
【版本:spring-boot-2.1.3.RELEASE】 深入Spring Boot核心组件 Spring Boot是一个流行的框架,简化了基于Spring的应用程序的开发和部署。它通过自动配置和“开箱即用”的特性,使得开发者可以快速启动和运行应用程序。在Spring Boot中&#x…...
JVM 调优不再难:AI 工具自动生成内存优化方案
在 Java 应用程序的开发与运行过程中,Java 虚拟机(JVM)的性能调优一直是一项极具挑战性的任务,尤其是内存优化方面。不合适的 JVM 内存配置可能会导致应用程序出现性能瓶颈,甚至频繁抛出内存溢出异常,影响业…...
分层式设备控制架构、分布式微服务架构及插件化架构
在现代高端装备制造(如半导体设备、精密自动化系统)中,分层式设备控制架构、分布式微服务架构和插件化架构是提升系统灵活性、实时性和可扩展性的核心技术。以下从设计原理、实现方式及行业应用三个维度展开说明:  1.…...
上门服务 APP 30 亿营收商业模式在乌干达的技术赋能与实践
不久前,非洲乌干达出现黑人女技师提供上门足疗服务的消息引发关注。据了解,当地一次40分钟的上门按摩服务仅需约40元人民币,价格仅为国内同类服务的十分之一。这一现象折射出全球健康服务行业正在经历的数字化转型浪潮。 国内领先的上门服务平…...
Chemical Review IF=51.4 综述 | 柔性机器人的当下与未来:材料、技术与应用的深度融合
2025.03.31. 新加坡南洋理工大学研究团队在《Chemical Reviews》期刊上发表 “Soft Materials and Devices Enabling Sensorimotor Functions in Soft Robots” 综述型文章。软机器人的传感器运动功能对其与环境交互至关重要,本文全面综述了相关软材料和设备。传感技…...
Python抽象基类
abstractmethod 详解 abstractmethod 是 Python 中 abc 模块(Abstract Base Classes,抽象基类)提供的一个装饰器,用于定义抽象方法。抽象方法是一种在基类中声明但不实现具体逻辑的方法,强制子类必须实现该方法。以下…...
计算机网络中各种物理量的单位总结
在计算机网络中,数据速率的单位容易混淆,以下是清晰总结: 一、基本单位区分 比特(bit)与字节(Byte) 小写 b 表示 比特(bit),是数据传输的基本单位。 大写 B…...
PCIE网卡驱动DMA初始化配置
1. DMA 启用的时机 e1000e 驱动在 设备初始化阶段 启用 DMA,具体步骤如下: (1) PCIe 设备初始化 调用路径: e1000_probe() → e1000_sw_init() → e1000_init_hw() → e1000_configure() 关键操作: 启用 PCIe 设备的 DMA 主控模…...
音视频小白系统入门笔记-1
本系列笔记为博主学习李超老师课程的课堂笔记,仅供参阅 课程传送门:音视频小白系统入门课 音视频基础ffmpeg原理 往期课程笔记传送门:音视频小白系统入门笔记-0 课程实践代码仓库:传送门 音频采集 命令行采集 Android端音频…...
技术速递|使用 BrowserStack App Automate 和 Appium UI 测试 .NET MAUI 应用
作者:Sweeky&Gerald 排版:Alan Wang 本文是 Gerald 的博客《开始使用 Appium 测试 .NET MAUI 应用的 UI 》中创建的 .NET MAUI – 使用 Appium 和 NUnit 进行 UI 测试的续篇。 在本篇博客中,我们将了解如何使用 BrowserStack App Automa…...
在多系统环境中实现授权闭环,Tetra Pak 借助CodeMeter打造食品工业的安全自动化体系
一、 行业背景与安全新挑战 在食品加工自动化不断深化的背景下,食品安全、功能安全与知识产权保护的需求日益迫切。Tetra Pak 作为全球领先的食品加工和包装解决方案提供商,业务遍布 160 多个国家,涵盖从配料混合、碳酸化处理到全线自动包装。…...
Nginx+SpringBoot跨域那些事儿(多域名跨域加强版——Nginx配置详解)
嘿,小伙伴们,咱们接着上回书说到,当你的应用需要支持多个域名跨域访问时,Nginx+SpringBoot这对黄金搭档绝对是你的不二之选!今天,咱们就深入聊聊如何在Nginx中配置多个域名跨域,让你的应用更加灵活、强大! 一、跨域问题再科普(多域名跨域场景) 在前后端分离开发中,…...
基于Python的App流量大数据分析与可视化方案
一、引言 App流量数据通常包括用户的访问时间、停留时间、点击行为、页面跳转路径等信息。这些数据分散在不同的服务器日志、数据库或第三方数据平台中,需要通过有效的技术手段进行整合和分析。Python在数据科学领域的广泛应用,得益于其简洁的语法、强大…...
windows下使用nginx + waitress 部署django
架构介绍 linux一般采用nginx uwsgi部署django,在Windows下,可以取代uwsgi的选项包括Waitressa、Daphnea、Hypercoma和Gunicorna(通过WSLa 运行)。windows服务器一般采用nginx waitress 部署django,,他们的关系如下 django是WEB应用…...
openssh离线一键升级脚本分享(含安装包)
查看当前的版本 [rootmyoracle ~]#ssh -V相关安装包下载地址 openssh下载地址:http://ftp.openbsd.org/pub/OpenBSD/OpenSSH/portable/openssl下载地址:https://www.openssl.org/source/zlib下载地址:http://www.zlib.net/今天演示从7.4升级…...
【专题刷题】双指针(二)
📝前言说明: 本专栏主要记录本人的基础算法学习以及LeetCode刷题记录,按专题划分每题主要记录:(1)本人解法 本人屎山代码;(2)优质解法 优质代码;ÿ…...
Ubuntu服务器中了木马且处于局域网内无法直接通过公网正向连接
如果你的Ubuntu服务器中了木马且处于局域网内无法直接通过公网正向连接,可以尝试以下方法进行应急响应和恢复控制: 一、尝试通过局域网内部访问(优先方案) 如果攻击者未完全封锁你的权限,且你有局域网内其他机器的控制权: 通过跳板机连接: 使用同一局域网内的其他机器…...
Day09 【基于LSTM实现文本加标点的任务】
基于LSTM实现文本加标点的任务 目标数据准备参数配置数据处理模型构建定义模型结构前向传播方法优化器选择 主程序测试与评估类初始化模型评估统计记录显示统计结果 测试结果 目标 本文基于给定的词表,将输入的文本基于jieba分词分割为若干个词,然后基于…...
SQL刷题日志(day2)
1、timestampdiff:计算时间间隔 timestampdiff(unit,start_date,end_date) 参数说明: unit:返回的时间单位,如minute,hour等start_date:开始日期end_date:结束日期 2、dense_rank(ÿ…...
仿 ElementUI 搭建自己的 vue 组件库
仿 ElementUI 搭建自己的 vue 组件库 一、创建 my-ui-can 项目1. 新建项目2. 自定义组件3. 创建 MyButton 组件4. 导出组件5. package.json 二、发布到 npm 仓库1. npm 账号注册(忽略)2. 发布 my-ui-can 二、项目引用 my-ui-can 依赖包方式一:…...
CentOS 操作系统下搭建 tsung性能测试环境
写在前面 为何这么安装,实际就是这么做的,这是经过好几次实践得出的经验总结。 这为了让大家更清楚的知道怎么安装 tsung性能测试环境,按步照搬的安装即可。 步骤 1、 下载软件安装包 CentOS-6.0-x86_64-bin-DVD1.iso jdk-6u4-linux-x64-rpm.bin erlang: otp_src_1…...
基于YOLOv9的课堂行为检测系统
基于YOLOv9的课堂行为检测系统 项目概述 本项目是一个基于YOLOv9深度学习模型的课堂行为检测系统,旨在通过计算机视觉技术自动识别和监测课堂中学生的各种行为状态,帮助教师更好地了解课堂教学效果。 项目结构 课堂行为检测/ ├── data/ │ ├──…...
Linux常见工具的基本使用,同时介绍了编译过程和动/静态链接的原理
目录 一、工具的本质 二、一些常用的工具 1.yum 2.vim 1)vim的三种基本模式: 2)vim的基本操作 ①命令模式下的基本操作: ②插入模式: ③底行模式: 3)vim的配置:让他变得更好用 3.gcc…...
6.(vue3.x+vite)动态挂载组件并传递参数和方法
1:效果截图 2:父组件代码 <template><div id="cesiumID"></div><div>子组件使用方法传递给父组件的值:{...
大数据人工智能
在大数据人工智能领域,需要具备多种算法和深度学习知识,以下是一些常见的: 机器学习算法 - 线性回归:用于建立输入特征与连续型输出变量之间的线性关系,常用于预测数值型数据。 - 逻辑回归:主要用于二分类…...
Vue3 nextTick
nextTick 是 Vue 中非常重要的一个 API,它允许你在 DOM 更新周期后执行延迟回调。 核心源码位置 Vue3 的 nextTick 实现主要在 packages/runtime-core/src/scheduler.ts 文件中。 基本实现 const resolvedPromise Promise.resolve() as Promise<any> let …...
快速入手-基于python和opencv的人脸检测
1、安装库 pip install opencv-python 如果下载比较卡的话,指向国内下载地址: pip3 install opencv-python -i https://pypi.tuna.tsinghua.edu.cn/simple 2、下载源码 https://opencv.org/ windows11对应的版本下载: https://pan.baidu…...
第七节:React HooksReact 18+新特性-并发模式(Concurrent Mode)解决了什么问题?
• 考点:可中断渲染、优先级调度、startTransition使用场景 • 示例:搜索框输入防抖优化 React Hooks 进阶:自定义 Hook 设计实战指南(以 useWindowSize 和 useFetch 为例) 一、自定义 Hook 设计规范 在实现 useWind…...
jwt的无感刷新
jwt无感刷新 如果没有引入额外的刷新机制,JWT 过期后后续请求就会因验证失败而拒绝,导致用户需要重新登录,从而被“强制下线”。为实现无感刷新,可以考虑以下几种方案: 引入 Refresh Token 双 token 机制:…...
Linux:安装 CentOS 7(完整教程)
文章目录 一、简介二、安装 CentOS 72.1 虚拟机配置2.2 安装CentOS 7 三、连接远程服务器(扩展)3.1 获取虚拟机 IP 地址3.2 连接远程服务器 四、结语 一、简介 CentOS(Community ENTerprise Operating System)是一个基于 Linux 的…...
【YOLOv8改进- Backbone主干】CVPR2025 MambaOut :为图像分类任务设计的轻量级模型,曼巴永存!
YOLOV8目标检测创新改进与实战案例专栏 专栏目录: YOLOV8有效改进系列及项目实战目录 包含卷积,主干 注意力,检测头等创新机制 以及 各种目标检测分割项目实战案例 专栏链接: YOLOV8基础解析+创新改进+实战案例 介绍 摘要 “曼巴(Mamba)是一种具有状态空间模型(SSM)的…...
thanos与VictoriaMetrics对比
Thanos 和 VictoriaMetrics 都是开源的时序数据库(TSDB)解决方案,通常用于存储、查询和管理大规模的时间序列数据,尤其是监控数据。尽管它们在功能上有一些重叠,但它们各自的设计目标、架构、以及适用场景存在差异。以…...
ubuntu 24.02部署java web服务
ubuntu 24.02 版本推荐使用jdk 21版本部署java web服务,开发后先使用sudo java -jar xxx.jar验证运行结果。 jdk安装:sudo apt install openjdk-21-jdk-headless 编辑服务文本 [Unit] DescriptionWebMgr Java Application Afternetwork.target mysql.…...