二叉树遍历
二叉树的遍历是二叉树操作中的一个基本且重要的概念,它指的是按照一定的规则访问二叉树中的每个节点,并且每个节点仅被访问一次。常见的二叉树遍历方式有四种:前序遍历(Pre-order Traversal)、中序遍历(In-order Traversal)、后序遍历(Post-order Traversal)和层序遍历(Level-order Traversal)。
1. 前序遍历(Pre-order Traversal)
前序遍历的顺序是:根节点 -> 左子树 -> 右子树。对于每个节点,都遵循这个顺序进行遍历。
- 递归实现:
void preorderTraversal(TreeNode root) { if (root == null) return; System.out.print(root.val + " "); // 访问根节点 preorderTraversal(root.left); // 遍历左子树 preorderTraversal(root.right); // 遍历右子树 } - 非递归(迭代)实现(使用栈):
void preorderTraversalIterative(TreeNode root) { Stack<TreeNode> stack = new Stack<>(); if (root != null) 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. 中序遍历(In-order Traversal)
中序遍历的顺序是:左子树 -> 根节点 -> 右子树。这常用于二叉搜索树(BST)中,因为这样可以得到一个有序的节点序列。
- 递归实现
void inorderTraversal(TreeNode root) { if (root == null) return; inorderTraversal(root.left); // 遍历左子树 System.out.print(root.val + " "); // 访问根节点 inorderTraversal(root.right); // 遍历右子树 } - 非递归(迭代)实现(使用栈):
void inorderTraversalIterative(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. 后序遍历(Post-order Traversal)
后序遍历的顺序是:左子树 -> 右子树 -> 根节点。
- 递归实现:
void postorderTraversal(TreeNode root) { if (root == null) return; postorderTraversal(root.left); // 遍历左子树 postorderTraversal(root.right); // 遍历右子树 System.out.print(root.val + " "); // 访问根节点 } - 非递归(迭代)实现(使用栈):
void postorderTraversalIterative(TreeNode root) { Stack<TreeNode> stack = new Stack<>(); TreeNode prev = null; // 用于记录上一次访问的节点 while (root != null || !stack.isEmpty()) { while (root != null) { stack.push(root); root = root.left; // 遍历到最左节点 } root = stack.peek(); // 弹出栈顶元素但不移除 // 如果右子树为空或者右子树已经访问过,则访问当前节点 if (root.right == null || root.right == prev) { stack.pop(); System.out.print(root.val + " "); // 访问节点 prev = root; root = null; // 回到上层循环,检查是否有其他节点需要访问 } else { root = root.right; // 否则,转向右子树 } } }4. 层序遍历
-
非递归(迭代)实现(使用队列)
import java.util.LinkedList; import java.util.Queue; class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public class BinaryTreeLevelOrderTraversal { public void levelOrderTraversal(TreeNode root) { if (root == null) return; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); // 将根节点加入队列 while (!queue.isEmpty()) { TreeNode currentNode = queue.poll(); // 从队列中取出一个节点 System.out.print(currentNode.val + " "); // 访问该节点 // 如果左子节点不为空,则将其加入队列 if (currentNode.left != null) { queue.offer(currentNode.left); } // 如果右子节点不为空,则将其加入队列 if (currentNode.right != null) { queue.offer(currentNode.right); } } } } -
非递归(迭代)实现
-
实际上,层序遍历不常使用递归实现,因为递归本质上是栈的操作,而层序遍历需要的是队列。但我们可以借助一些额外的数据结构(如数组或链表)来模拟层序遍历的效果,但这通常不是推荐的做法,因为它违背了层序遍历的本意。
相关文章:
二叉树遍历
二叉树的遍历是二叉树操作中的一个基本且重要的概念,它指的是按照一定的规则访问二叉树中的每个节点,并且每个节点仅被访问一次。常见的二叉树遍历方式有四种:前序遍历(Pre-order Traversal)、中序遍历(In-…...
uni app 调用前置摄像头
uniapp开发app并没有相关Api调用前置摄像头。只能使用5app的api 调用前置摄像头拍照 plus.camera.getCamera(index) 获取需要操作的摄像头对象,如果要进行拍照或摄像操作,需先通过此方法获取摄像头对象 index指定要获取摄像头的索引值,1表…...
哈工大李治军老师OS课程笔记(4)——内存管理
一 内存使用与分段(实验六) 内存是如何用起来的? 内存使用:将程序放在内存中,PC指向开始地址 重定位:修改程序中的地址(是相对地址) 什么时候完成重定位? 编译时加基址…...
代码随想录算法训练营第43天:动态规划part10:子序列问题
300.最长递增子序列 力扣题目链接(opens new window) 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2…...
传智教育引通义灵码进课堂,为技术人才教育学习提效
7 月 17 日,阿里云与传智教育在阿里巴巴云谷园区签署合作协议,双方将基于阿里云智能编程助手通义灵码在课程共建、品牌合作及产教融合等多个领域展开合作,共同推进 AI 教育及相关业务的发展,致力于培养适应未来社会需求的高素质技…...
企业信息化建设搞得好了叫系统工程,搞不好叫面子工程
2024-06-13 09:26贝格前端工场...
程序员如何平衡日常编码工作与提升式学习?
在快速变化的编程领域中,平衡日常编码工作与个人成长确实是一个重要且富有挑战性的议题。以下是我对这一问题的看法和建议: 1. 认识到平衡的重要性 首先,理解两者之间的平衡并非零和游戏,而是相辅相成的。高效的编码工作能够为个…...
Linux---文件系统和日志分析
文章目录 文件系统和日志分析inode和block概述inode包含文件的元信息用stat命令可以查看某个文件的inode信息Linux系统文件三个主要的时间属性 目录文件的结构用户通过文件名打开文件时,系统内部的过程查看inode号码的方法硬盘分区后的结构访问文件的简单流程inode的…...
MySQL 体系架构
文章目录 一. MySQL 分支与变种1. Drizzle2. MariaDB3. Percona Server 二. MySQL的替代1. Postgre SQL2. SQLite 三. MySQL 体系架构1.连接层2 Server层(SQL处理层)3. 存储引擎层1)MySQL官方存储引擎概要2)第三方引擎3࿰…...
跨站脚本攻击漏洞
1.JavaScript JavaScript 是一种脚本,一门编程语言,它可以在网页上实现复杂的功能,网页展现给你的不再是简单的静态信息,而是实时的内容更新,交互式的地图,2D/3D动画,滚动播放的视频等等。 &a…...
RabbitMQ入门与进阶
RabbitMQ入门与进阶 基础篇1. 为什么需要消息队列?2. 什么是消息队列?3. RabbitMQ体系结构介绍4. RabbitMQ安装5. HelloWorld6. RabbitMQ经典用法(工作模式)7. Work Queues8. Publish/Subscribe9. Routing10. Topics 进阶篇1. RabbitMQ整合SpringBoot2. 消息可靠性投递故障情…...
Unity新输入系统 之 InputActions(输入配置文件)
本文仅作笔记学习和分享,不用做任何商业用途 本文包括但不限于unity官方手册,unity唐老狮等教程知识,如有不足还请斧正 首先你应该了解新输入系统的基本单位Unity新输入系统 之 InputAction(输入配置文件最基本的单位࿰…...
Linux运维篇-误删/bin,/sbin目录怎么修复系统
这里写自定义目录标题 前言实例挂载镜像,重启系统进入救援模式拷贝镜像系统中的/bin和/sbin目录到原系统重启系统 总结 前言 当你看到这篇文章的时候,你的系统可能已经无法登录,或者正在处于登录状态但是不能执行任何常规的命令,…...
构建高效外贸电商系统的技术探索与源码开发
在当今全球化的经济浪潮中,外贸电商作为连接国内外市场的桥梁,其重要性日益凸显。一个高效、稳定、功能全面的外贸电商系统,不仅能够助力企业突破地域限制,拓宽销售渠道,还能提升客户体验,增强品牌竞争力。…...
Java设计模式:中介者模式详解与最佳实践
Java设计模式:中介者模式详解与最佳实践 1. 引言 在软件开发过程中,特别是复杂系统的构建中,模块间的交互往往成为影响代码质量的重要因素。当模块之间耦合度过高时,系统的维护、扩展和理解成本都会显著增加。为了降低模块之间的…...
Matlab绘制像素风字母颜色及透明度随机变化动画
本文是使用 Matlab 绘制像素风字母颜色及透明度随机变化动画的教程 实现效果 实现代码 如果需要更改为其他字母组合,在下面代码的基础上简单修改就可以使用。 步骤:(1) 定义字母形状;(2) 给出字母组合顺序;(3) 重新运行程序&#…...
C:每日一题:二分查找
1、知识介绍: 1.1 概念: 二分查找是一种在有序数组中查找某一特定元素的搜索算法 1.2 基本思想: 每次将待查找的范围缩小一半,通过比较中间元素与目标元素的大小,来决定是在左半部分还是右半部分继续查找。 举个生…...
python Django中使用ORM进行分组统计并降序排列
python Django中使用ORM进行分组统计并降序排列 # 使用supplier和Count进行分组统计,其中supplier为MyModel的一个字段 supplier_counts MyModel.objects.values(supplier).annotate(countCount(supplier)).order_by(-count) # 输出统计结果 for supplier_count in supplier_…...
QT C++ 编写modbus 总结
[开源库的使用]libModbus编译及使用_libmodbus库-CSDN博客 libmodbus的下载与编译_modbus库文件下载-CSDN博客 【QT5】解决 QT 界面中文显示乱码问题_qt5输出中文乱码解决方法-CSDN博客 Qt:解决qt修改完ui文件起不到作用_qt ui文件修改后不生效-CSDN博客...
基于SpringBoot的网络海鲜市场系统的设计与实现
TOC springboot219基于SpringBoot的网络海鲜市场系统的设计与实现 绪论 1.1 选题背景 当人们发现随着生产规模的不断扩大,人为计算方面才是一个巨大的短板,所以发明了各种计算设备,从结绳记事,到算筹,以及算盘&…...
逻辑回归:给不确定性划界的分类大师
想象你是一名医生。面对患者的检查报告(肿瘤大小、血液指标),你需要做出一个**决定性判断**:恶性还是良性?这种“非黑即白”的抉择,正是**逻辑回归(Logistic Regression)** 的战场&a…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...
Docker 运行 Kafka 带 SASL 认证教程
Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明:server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...
dedecms 织梦自定义表单留言增加ajax验证码功能
增加ajax功能模块,用户不点击提交按钮,只要输入框失去焦点,就会提前提示验证码是否正确。 一,模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...
微信小程序 - 手机震动
一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注:文档 https://developers.weixin.qq…...
【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表
1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...
【单片机期末】单片机系统设计
主要内容:系统状态机,系统时基,系统需求分析,系统构建,系统状态流图 一、题目要求 二、绘制系统状态流图 题目:根据上述描述绘制系统状态流图,注明状态转移条件及方向。 三、利用定时器产生时…...
【Java学习笔记】BigInteger 和 BigDecimal 类
BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点:传参类型必须是类对象 一、BigInteger 1. 作用:适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...
十九、【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建
【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建 前言准备工作第一部分:回顾 Django 内置的 `User` 模型第二部分:设计并创建 `Role` 和 `UserProfile` 模型第三部分:创建 Serializers第四部分:创建 ViewSets第五部分:注册 API 路由第六部分:后端初步测…...
k8s从入门到放弃之Pod的容器探针检测
k8s从入门到放弃之Pod的容器探针检测 在Kubernetes(简称K8s)中,容器探测是指kubelet对容器执行定期诊断的过程,以确保容器中的应用程序处于预期的状态。这些探测是保障应用健康和高可用性的重要机制。Kubernetes提供了两种种类型…...
