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

算法日记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);}
}
  1. resList 定义和初始化

    • public List<List<Integer>> resList = new ArrayList<List<Integer>>();
    • 定义了一个成员变量 resList,用于存储二叉树的层次遍历结果。初始化为空的 ArrayList,用于存储每一层的节点值列表。
  2. levelOrder 方法

    • public List<List<Integer>> levelOrder(TreeNode root)
    • 主方法,调用 test 方法进行二叉树的层次遍历,并返回最终的层次遍历结果 resList
  3. 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(二叉树的广度优先遍历|反转、对称二叉树)

一、二叉树的层序遍历 题目&#xff1a; 给你二叉树的根节点 root &#xff0c;返回其节点值的 层序遍历 。 &#xff08;即逐层地&#xff0c;从左到右访问所有节点&#xff09;。 示例 1&#xff1a; 输入&#xff1a;root [3,9,20,null,null,15,7] 输出&#xff1a;[[3]…...

PolarisMesh源码系列--Polaris-Go注册发现流程

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

vue3 vxe-grid修改currentPage,查询数据的时候,从第一页开始查询

1、当我们设置好VxeGrid.Options进行数据查询的时候,下面是可能的设置&#xff1a; const gridOptions reactive<BasicTableProps>({id: UserTable,showHeaderOverflow: false,showOverflow: true,keepSource: true,columns: userColumns,size: small,pagerConfig: {cur…...

电商数据集成之电商商品信息采集系统架构设计||电商API接口

一、引言 本架构设计文档旨在阐述基于 Selenium 的电商商品信息采集系统的整体架构&#xff0c;包括系统视图、逻辑视图、物理视图、开发视图和进程视图&#xff0c;并提供一个简单的采集电商商品信息的 demo。该系统通过模拟浏览器行为&#xff0c;实现对电商商品信息的自…...

Spring Cloud Stream 实现统一消息通信平台

1. 概述 Spring Cloud Stream&#xff1a;是Spring提供的消息通信框架&#xff0c;旨在构建跨不同消息中间件的统一通信平台。目的&#xff1a;通过消息通信机制降低分布式系统中服务间的耦合度&#xff0c;实现异步服务交互。 2. 消息通信与RPC RPC&#xff1a;远程过程调用…...

uniapp安卓plus原生选择系统文件

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

Go语言 Import导入

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

一款异次元小清新风格的响应式wordpress个人博客主题

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

【cocos creator】ts中export的模块管理

在 TypeScript&#xff08;TS&#xff09;中&#xff0c;export 和 import 的概念与 Java 中的 public 类、接口以及 import 语句有一些相似之处。可以用以下方式来类比理解&#xff1a; Export 在 TypeScript 中&#xff0c;export 用于将模块中的变量、函数、类等暴露给外部…...

QT JSON使用实例

下面是一个使用Qt框架的示例代码&#xff0c;展示如何获取仪器的状态&#xff0c;将其打包成JSON格式&#xff0c;保存到当前目录下的JSON文件中&#xff0c;然后通过FTP发送该文件。 1. 准备工作 确保你已经安装了Qt&#xff0c;并创建一个新的Qt Console项目或Qt Widgets项目…...

浅聊 Three.js 屏幕空间反射SSR-SSRShader

浅聊 Three.js 屏幕空间反射SSR(2)-SSRShader 前置基础 渲染管线中的相机和屏幕示意图 -Z (相机朝向的方向)||| -------------- <- 屏幕/投影平面| | || | || | (f) | <- 焦距| | ||…...

Windows图形界面(GUI)-DLG-C/C++ - 月历控件(MonthCalendar)

公开视频 -> 链接点击跳转公开课程博客首页 -> e​​​​​​链接点击跳转博客主页 目录 月历控件(MonthCalendar) 使用场景 控件操作 月历控件(MonthCalendar) 使用场景 日程安排&#xff1a;用户可以通过月历控件选择特定的日期来安排会议或活动。事件管理&#x…...

【Langchain大语言模型开发教程】基于文档问答

&#x1f517; LangChain for LLM Application Development - DeepLearning.AI Embedding&#xff1a; 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推流视频到网页端

参考&#xff1a; Luckfox-Pico/Luckfox-Pico-RV1103/Luckfox-Pico-pinout/CSI-Camera Luckfox-Pico/RKMPI-example Luckfox-Pico/RKMPI-example 下载源码 其中源码位置&#xff1a;https://github.com/luckfox-eng29/luckfox_pico_rtsp_opencv 使用git clone由于项目比较大&am…...

与Bug较量:Codigger之软件项目体检Software Project HealthCheck来帮忙

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

Git --- Branch Diverged

Git --- Branch Diverged Branch Diverged是如何形成的如何解决RebaseMerge Branch Diverged是如何形成的 尝试提交并将更改推送到 master 分支时&#xff0c;是否看到这条烦人的消息 原因是&#xff1a; 直到更改 B 之前&#xff0c;我的分支和“origin/master”完全相同。从…...

go标准库---net/http服务端

1、http简单使用 go的http标准库非常强大&#xff0c;调用了两个函数就能够实现一个简单的http服务&#xff1a; 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>自动补全 在敲出 文件/目录/命令 的前几个字母之后&#xff0c;按下…...

【C++刷题】优选算法——链表

链表常用技巧和操作总结 常用技巧 画图 引入虚拟头节点 不要吝啬空间&#xff0c;大胆定义变量 快慢双指针常用操作 创建一个新节点 尾插 头插 两数相加 ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {int carry 0;ListNode* newHead new ListNode, *cur newHea…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

AspectJ 在 Android 中的完整使用指南

一、环境配置&#xff08;Gradle 7.0 适配&#xff09; 1. 项目级 build.gradle // 注意&#xff1a;沪江插件已停更&#xff0c;推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

浪潮交换机配置track检测实现高速公路收费网络主备切换NQA

浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求&#xff0c;本次涉及的主要是收费汇聚交换机的配置&#xff0c;浪潮网络设备在高速项目很少&#xff0c;通…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别

【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而&#xff0c;传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案&#xff0c;能够实现大范围覆盖并远程采集数据。尽管具备这些优势&#xf…...

虚拟电厂发展三大趋势:市场化、技术主导、车网互联

市场化&#xff1a;从政策驱动到多元盈利 政策全面赋能 2025年4月&#xff0c;国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》&#xff0c;首次明确虚拟电厂为“独立市场主体”&#xff0c;提出硬性目标&#xff1a;2027年全国调节能力≥2000万千瓦&#xff0…...

多模态图像修复系统:基于深度学习的图片修复实现

多模态图像修复系统:基于深度学习的图片修复实现 1. 系统概述 本系统使用多模态大模型(Stable Diffusion Inpainting)实现图像修复功能,结合文本描述和图片输入,对指定区域进行内容修复。系统包含完整的数据处理、模型训练、推理部署流程。 import torch import numpy …...

PHP 8.5 即将发布:管道操作符、强力调试

前不久&#xff0c;PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5&#xff01;作为 PHP 语言的又一次重要迭代&#xff0c;PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是&#xff0c;借助强大的本地开发环境 ServBay&am…...

HubSpot推出与ChatGPT的深度集成引发兴奋与担忧

上周三&#xff0c;HubSpot宣布已构建与ChatGPT的深度集成&#xff0c;这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋&#xff0c;但同时也存在一些关于数据安全的担忧。 许多网络声音声称&#xff0c;这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...