当前位置: 首页 > 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…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

C++.OpenGL (10/64)基础光照(Basic Lighting)

基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建

华为云FlexusDeepSeek征文&#xff5c;DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色&#xff0c;华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型&#xff0c;能助力我们轻松驾驭 DeepSeek-V3/R1&#xff0c;本文中将分享如何…...

安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)

船舶制造装配管理现状&#xff1a;装配工作依赖人工经验&#xff0c;装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书&#xff0c;但在实际执行中&#xff0c;工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...

智能AI电话机器人系统的识别能力现状与发展水平

一、引言 随着人工智能技术的飞速发展&#xff0c;AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术&#xff0c;在客户服务、营销推广、信息查询等领域发挥着越来越重要…...

iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈

在日常iOS开发过程中&#xff0c;性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期&#xff0c;开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发&#xff0c;但背后往往隐藏着系统资源调度不当…...

Java数值运算常见陷阱与规避方法

整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...