算法日记day 16(二叉树的广度优先遍历|反转、对称二叉树)
一、二叉树的层序遍历
题目:
给你二叉树的根节点 root
,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。
示例 1:
输入:root = [3,9,20,null,null,15,7] 输出:[[3],[9,20],[15,7]]
示例 2:
输入:root = [1] 输出:[[1]]
示例 3:
输入:root = [] 输出:[]
思路:
用队列来存储元素,变量size来存储每一层的元素个数,扫描队头元素,判断其是否有左右孩子,如果有,将其入队,同时该队头元素出队,记录在该层所封装的结果集中,同时size减一,当size值减为0时,说明该层所有元素均遍历完毕,返回结果集
代码:
// 结果列表,用于存储每一层的节点值列表
public List<List<Integer>> resList = new ArrayList<List<Integer>>();// 主方法,进行二叉树的层次遍历
public List<List<Integer>> levelOrder(TreeNode root) {// 调用辅助方法进行层次遍历test(root);// 返回结果列表return resList;
}// 辅助方法,实现二叉树的层次遍历
public void test(TreeNode root) {// 如果根节点为空,直接返回if (root == null)return;// 创建队列,用于存储待处理的节点Queue<TreeNode> queue = new LinkedList<>();queue.add(root); // 将根节点加入队列// 循环处理队列中的节点,直到队列为空while (!queue.isEmpty()) {// 用于存储当前层节点值的列表List<Integer> list = new LinkedList<>();int len = queue.size(); // 当前层节点的数量// 处理当前层的所有节点while (len > 0) {TreeNode tnode = queue.poll(); // 出队列,获取当前处理的节点list.add(tnode.val); // 将节点值加入当前层的列表// 将当前节点的左右子节点加入队列,用于下一层处理if (tnode.left != null)queue.add(tnode.left);if (tnode.right != null)queue.add(tnode.right);len--; // 当前层节点数减一}// 将当前层的节点值列表加入结果列表resList.add(list);}
}
-
resList 定义和初始化:
public List<List<Integer>> resList = new ArrayList<List<Integer>>();
- 定义了一个成员变量
resList
,用于存储二叉树的层次遍历结果。初始化为空的ArrayList
,用于存储每一层的节点值列表。
-
levelOrder 方法:
public List<List<Integer>> levelOrder(TreeNode root)
- 主方法,调用
test
方法进行二叉树的层次遍历,并返回最终的层次遍历结果resList
。
-
test 方法:
public void test(TreeNode root)
- 辅助方法,实现二叉树的层次遍历。
- 使用队列
queue
进行广度优先搜索(BFS):- 首先将根节点加入队列。
- 每次处理队列中的一个节点,将其值加入当前层的
list
中,并将其左右子节点(如果存在)加入队列。 - 每处理完一层的所有节点后,将当前层的节点值列表
list
加入resList
中。
二、翻转二叉树
题目:
给你一棵二叉树的根节点 root
,翻转这棵二叉树,并返回其根节点。
示例 1:
输入:root = [4,2,7,1,3,6,9] 输出:[4,7,2,9,6,3,1]
示例 2:
输入:root = [2,1,3] 输出:[2,3,1]
示例 3:
输入:root = [] 输出:[]
思路:
可以采用递归前序和后序遍历的方法,遍历一个结点的同时反转其左右子节点,接着往下一层移动,重复以上操作,直到遍历到的节点为空停止
代码:
//前序
public TreeNode invertTree(TreeNode root) {if (root == null)return root;swap(root); // 调用 swap 方法,交换当前节点的左右子节点 中invertTree(root.left); // 递归翻转左子树 左invertTree(root.right); // 递归翻转右子树 右return root; // 返回翻转后的根节点
}
public void swap(TreeNode root) {TreeNode temp = root.left;root.left = root.right;root.right = temp;
}
后序遍历方法类似,只需将顺序修改为左,右,中即可
用中序遍历的方法稍有不同,由于中序是左,中,右的顺序,当返回到根节点时左右子树交换顺序,此时应该继续遍历右子树,但是这时的右子树正好是刚刚交换完的左子树 ,因此实际上仅是交换了一次左子树,要想实现反转,必须再次进行左子树的交换操作即可,代码如下:
invertTree(root.left); // 递归翻转左子树 左
swap(root); // 调用 swap 方法,交换当前节点的左右子节点 中
invertTree(root.left); // 这时再次操作反转后的左子树 右
三、对称二叉树
题目:
给你一个二叉树的根节点 root
, 检查它是否轴对称。
示例 1:
输入:root = [1,2,2,3,4,4,3] 输出:true
示例 2:
输入:root = [1,2,2,null,3,null,3] 输出:false
思路:
采用后序遍历的方法,为什么要采用后序呢?由于后序遍历的顺序是左,右,中,而要判断二叉树是否对称就是要判断根节点的左右子树是否在翻转后可以重合,后序的遍历顺序正好可以判断左右子树,再在最后遍历根节点,具体方法是,先遍历根节点的左右子节点是否相同,再判断左子节点的左子节点是否与右子节点的右子节点相同,同理再判断左子节点的右子节点是否和右子节点的左子节点相同,重复上述操作,直到为空
代码:
// 判断给定的二叉树是否对称的方法
public boolean isSymmetric(TreeNode root) {// 调用 compare 方法,比较根节点的左右子树是否对称return compare(root.left, root.right);
}// 递归比较两棵树是否对称的方法
public boolean compare(TreeNode left, TreeNode right) {// 边界情况处理:// 左子树不为空而右子树为空,或者左子树为空而右子树不为空,二叉树不对称,返回 falseif (left != null && right == null)return false;if (left == null && right != null)return false;// 左右子树都为空,认为对称,返回 trueif (left == null && right == null)return true;// 比较当前节点值是否相等,若不相等,二叉树不对称,返回 falseif (left.val != right.val)return false;// 递归比较左子树的左节点与右子树的右节点,外侧比较boolean Outcompare = compare(left.left, right.right);// 递归比较左子树的右节点与右子树的左节点,内侧比较boolean Intcompare = compare(left.right, right.left);// 返回外侧比较和内侧比较的与运算结果,确定整棵树是否对称return Outcompare && Intcompare;
}
- 首先处理边界情况:
- 如果
left
不为 null 而right
为 null,或者left
为 null 而right
不为 null,则二叉树不对称,返回false
。 - 如果
left
和right
都为 null,则认为是对称的,返回true
。
- 如果
- 然后比较当前节点的值
left.val
和right.val
是否相等,如果不相等,则二叉树不对称,返回false
。 - 如果当前节点值相等,继续递归比较
left
的左子节点left.left
和right
的右子节点right.right
是否对称(外侧比较)。 - 同时递归比较
left
的右子节点left.right
和right
的左子节点right.left
是否对称(内侧比较)。 - 最终返回外侧比较结果
Outcompare
和内侧比较结果Intcompare
的与运算结果,即判断整棵树是否对称。
相关资料:
https://www.programmercarl.com/0101.%E5%AF%B9%E7%A7%B0%E4%BA%8C%E5%8F%89%E6%A0%91.html
今天的学习就到这里了!
相关文章:

算法日记day 16(二叉树的广度优先遍历|反转、对称二叉树)
一、二叉树的层序遍历 题目: 给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。 示例 1: 输入:root [3,9,20,null,null,15,7] 输出:[[3]…...

PolarisMesh源码系列--Polaris-Go注册发现流程
导语 北极星是腾讯开源的一款服务治理平台,用来解决分布式和微服务架构中的服务管理、流量管理、配置管理、故障容错和可观测性问题。在分布式和微服务架构的治理领域,目前国内比较流行的还包括 Spring Cloud,Apache Dubbo 等。在 Kubernete…...

vue3 vxe-grid修改currentPage,查询数据的时候,从第一页开始查询
1、当我们设置好VxeGrid.Options进行数据查询的时候,下面是可能的设置: const gridOptions reactive<BasicTableProps>({id: UserTable,showHeaderOverflow: false,showOverflow: true,keepSource: true,columns: userColumns,size: small,pagerConfig: {cur…...

电商数据集成之电商商品信息采集系统架构设计||电商API接口
一、引言 本架构设计文档旨在阐述基于 Selenium 的电商商品信息采集系统的整体架构,包括系统视图、逻辑视图、物理视图、开发视图和进程视图,并提供一个简单的采集电商商品信息的 demo。该系统通过模拟浏览器行为,实现对电商商品信息的自…...
Spring Cloud Stream 实现统一消息通信平台
1. 概述 Spring Cloud Stream:是Spring提供的消息通信框架,旨在构建跨不同消息中间件的统一通信平台。目的:通过消息通信机制降低分布式系统中服务间的耦合度,实现异步服务交互。 2. 消息通信与RPC RPC:远程过程调用…...

uniapp安卓plus原生选择系统文件
uniapp安卓plus原生选择系统文件 效果: 组件代码: <template xlang"wxml" minapp"mpvue"><view></view> </template> <script>export default {name: file-manager,props: {},data() {return {is…...

Go语言 Import导入
本文主要介绍Go语言import导入使用时注意事项和功能实现示例。 目录 Import 创建功能文件夹 加法 减法 主函数 优化导入的包名 .引入方法 总结 Import 创建功能文件夹 做一个计算器来演示,首先创建test文件夹。 加法 在test文件夹中创建add文件夹ÿ…...

一款异次元小清新风格的响应式wordpress个人博客主题
一款异次元小清新风格的响应式个人博客主题。这是一款专注于用户阅读体验的响应式 WordPress 主题,整体布局简洁大方,针对资源加载进行了优化。 Kratos主题基于Bootstrap和Font Awesome的WordPress一个干净,简单且响应迅速的博客主题&#x…...

【cocos creator】ts中export的模块管理
在 TypeScript(TS)中,export 和 import 的概念与 Java 中的 public 类、接口以及 import 语句有一些相似之处。可以用以下方式来类比理解: Export 在 TypeScript 中,export 用于将模块中的变量、函数、类等暴露给外部…...
QT JSON使用实例
下面是一个使用Qt框架的示例代码,展示如何获取仪器的状态,将其打包成JSON格式,保存到当前目录下的JSON文件中,然后通过FTP发送该文件。 1. 准备工作 确保你已经安装了Qt,并创建一个新的Qt Console项目或Qt Widgets项目…...

浅聊 Three.js 屏幕空间反射SSR-SSRShader
浅聊 Three.js 屏幕空间反射SSR(2)-SSRShader 前置基础 渲染管线中的相机和屏幕示意图 -Z (相机朝向的方向)||| -------------- <- 屏幕/投影平面| | || | || | (f) | <- 焦距| | ||…...
Windows图形界面(GUI)-DLG-C/C++ - 月历控件(MonthCalendar)
公开视频 -> 链接点击跳转公开课程博客首页 -> e链接点击跳转博客主页 目录 月历控件(MonthCalendar) 使用场景 控件操作 月历控件(MonthCalendar) 使用场景 日程安排:用户可以通过月历控件选择特定的日期来安排会议或活动。事件管理&#x…...

【Langchain大语言模型开发教程】基于文档问答
🔗 LangChain for LLM Application Development - DeepLearning.AI Embedding: https://huggingface.co/BAAI/bge-large-en-v1.5/tree/main 学习目标 1、Embedding and Vector Store 2、RetrievalQA 引包、加载环境变量 import osfrom dotenv import…...

大厂面试-基本功
大厂面试第4季 服务可用性多少个9是什么意思遍历集合add或remove操作bughashcode冲突案例BigdecimalList去重复IDEA Debugger测试框架ThreaLocal父子线程数据同步 InheritableThreadLocal完美解决线程数据同步方案 TransmittableThreadLocal 服务可用性多少个9是什么意思 遍历集…...

RV1103使用rtsp和opencv推流视频到网页端
参考: Luckfox-Pico/Luckfox-Pico-RV1103/Luckfox-Pico-pinout/CSI-Camera Luckfox-Pico/RKMPI-example Luckfox-Pico/RKMPI-example 下载源码 其中源码位置:https://github.com/luckfox-eng29/luckfox_pico_rtsp_opencv 使用git clone由于项目比较大&am…...

与Bug较量:Codigger之软件项目体检Software Project HealthCheck来帮忙
在软件工程师的世界里,与 Java 小程序中的 Bug 作战是一场永不停歇的战役。每一个隐藏在代码深处的 Bug 都像是一个狡猾的敌人,时刻准备着给我们的项目带来麻烦。 最近,我就陷入了这样一场与 Java 小程序 Bug 的激烈较量中。这个小程序原本应…...

Git --- Branch Diverged
Git --- Branch Diverged Branch Diverged是如何形成的如何解决RebaseMerge Branch Diverged是如何形成的 尝试提交并将更改推送到 master 分支时,是否看到这条烦人的消息 原因是: 直到更改 B 之前,我的分支和“origin/master”完全相同。从…...
go标准库---net/http服务端
1、http简单使用 go的http标准库非常强大,调用了两个函数就能够实现一个简单的http服务: func HandleFunc(pattern string, handler func(ResponseWriter, *Request)) func ListenAndServe(addr string, handler Handler) error handleFunc注册一个路…...

Linux文件和目录常用命令
1.操作命令 查看目录内容 ls 切换目录 cd 创建和删除操作 touch rm mkdir 拷贝和移动文件 cp mv 查看文件内容 cat more grep 其他 echo 重定向 > 和 >> 管道 | 1.1 终端实用技巧 1>自动补全 在敲出 文件/目录/命令 的前几个字母之后,按下…...
【C++刷题】优选算法——链表
链表常用技巧和操作总结 常用技巧 画图 引入虚拟头节点 不要吝啬空间,大胆定义变量 快慢双指针常用操作 创建一个新节点 尾插 头插 两数相加 ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {int carry 0;ListNode* newHead new ListNode, *cur newHea…...
逻辑回归:给不确定性划界的分类大师
想象你是一名医生。面对患者的检查报告(肿瘤大小、血液指标),你需要做出一个**决定性判断**:恶性还是良性?这种“非黑即白”的抉择,正是**逻辑回归(Logistic Regression)** 的战场&a…...
postgresql|数据库|只读用户的创建和删除(备忘)
CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...
oracle与MySQL数据库之间数据同步的技术要点
Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异,它们的数据同步要求既要保持数据的准确性和一致性,又要处理好性能问题。以下是一些主要的技术要点: 数据结构差异 数据类型差异ÿ…...
Java 加密常用的各种算法及其选择
在数字化时代,数据安全至关重要,Java 作为广泛应用的编程语言,提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景,有助于开发者在不同的业务需求中做出正确的选择。 一、对称加密算法…...
数据库分批入库
今天在工作中,遇到一个问题,就是分批查询的时候,由于批次过大导致出现了一些问题,一下是问题描述和解决方案: 示例: // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

SpringTask-03.入门案例
一.入门案例 启动类: package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...
AspectJ 在 Android 中的完整使用指南
一、环境配置(Gradle 7.0 适配) 1. 项目级 build.gradle // 注意:沪江插件已停更,推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...

dify打造数据可视化图表
一、概述 在日常工作和学习中,我们经常需要和数据打交道。无论是分析报告、项目展示,还是简单的数据洞察,一个清晰直观的图表,往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server,由蚂蚁集团 AntV 团队…...
laravel8+vue3.0+element-plus搭建方法
创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...

如何在网页里填写 PDF 表格?
有时候,你可能希望用户能在你的网站上填写 PDF 表单。然而,这件事并不简单,因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件,但原生并不支持编辑或填写它们。更糟的是,如果你想收集表单数据ÿ…...