算法日记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…...
<6>-MySQL表的增删查改
目录 一,create(创建表) 二,retrieve(查询表) 1,select列 2,where条件 三,update(更新表) 四,delete(删除表…...
可靠性+灵活性:电力载波技术在楼宇自控中的核心价值
可靠性灵活性:电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中,电力载波技术(PLC)凭借其独特的优势,正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据,无需额外布…...
【论文阅读28】-CNN-BiLSTM-Attention-(2024)
本文把滑坡位移序列拆开、筛优质因子,再用 CNN-BiLSTM-Attention 来动态预测每个子序列,最后重构出总位移,预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵(S…...
让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比
在机器学习的回归分析中,损失函数的选择对模型性能具有决定性影响。均方误差(MSE)作为经典的损失函数,在处理干净数据时表现优异,但在面对包含异常值的噪声数据时,其对大误差的二次惩罚机制往往导致模型参数…...
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要: 近期,在使用较新版本的OpenSSH客户端连接老旧SSH服务器时,会遇到 "no matching key exchange method found", "n…...
深度学习水论文:mamba+图像增强
🧀当前视觉领域对高效长序列建模需求激增,对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模,以及动态计算优势,在图像质量提升和细节恢复方面有难以替代的作用。 🧀因此短时间内,就有不…...
MacOS下Homebrew国内镜像加速指南(2025最新国内镜像加速)
macos brew国内镜像加速方法 brew install 加速formula.jws.json下载慢加速 🍺 最新版brew安装慢到怀疑人生?别怕,教你轻松起飞! 最近Homebrew更新至最新版,每次执行 brew 命令时都会自动从官方地址 https://formulae.…...
消防一体化安全管控平台:构建消防“一张图”和APP统一管理
在城市的某个角落,一场突如其来的火灾打破了平静。熊熊烈火迅速蔓延,滚滚浓烟弥漫开来,周围群众的生命财产安全受到严重威胁。就在这千钧一发之际,消防救援队伍迅速行动,而豪越科技消防一体化安全管控平台构建的消防“…...
WebRTC调研
WebRTC是什么,为什么,如何使用 WebRTC有什么优势 WebRTC Architecture Amazon KVS WebRTC 其它厂商WebRTC 海康门禁WebRTC 海康门禁其他界面整理 威视通WebRTC 局域网 Google浏览器 Microsoft Edge 公网 RTSP RTMP NVR ONVIF SIP SRT WebRTC协…...
基于stm32F10x 系列微控制器的智能电子琴(附完整项目源码、详细接线及讲解视频)
注:文章末尾网盘链接中自取成品使用演示视频、项目源码、项目文档 所用硬件:STM32F103C8T6、无源蜂鸣器、44矩阵键盘、flash存储模块、OLED显示屏、RGB三色灯、面包板、杜邦线、usb转ttl串口 stm32f103c8t6 面包板 …...
