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

对称二叉树[简单]

优质博文:IT-BLOG-CN
在这里插入图片描述

一、题目

给你一个二叉树的根节点root, 检查它是否轴对称。

示例 1:

输入:root = [1,2,2,3,4,4,3]
输出:true

示例 2:

输入:root = [1,2,2,null,3,null,3]
输出:false

树中节点数目在范围[1, 1000]
-100 <= Node.val <= 100

进阶: 你可以运用递归和迭代两种方法解决这个问题吗?

二、代码

【1】递归: 我们将一个树的左右节点相同,转换为两个根节点具有相同的值,每个树的右子树都与另一个树的左子树镜像对称。我们通过一个递归函数,通过同步移动两个指针的方式来遍历树,rootLeftrootRight都指向一个树的根,然后rootLeft右移时,rootRight左移,rootLeft左移时,rootRight右移。检查rootLeftrootRight的值是否相等,如果相等再判断左右子树是否对称。

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean isSymmetric(TreeNode root) {return check(root, root);}private boolean check(TreeNode rootLeft, TreeNode rootRight) {if (rootLeft == null && rootRight == null) {return true;}if (rootLeft == null || rootRight == null) {return false;}return rootLeft.val == rootRight.val && check(rootLeft.left, rootRight.right) && check(rootLeft.right, rootRight.left);}
}
**时间复杂度:** 这里遍历了这棵树,渐进时间复杂度为`O(n)`。  
**空间复杂度:** 这里的空间复杂度和递归使用的栈空间有关,这里递归层数不超过`n`,故渐进空间复杂度为`O(n)`。

【2】迭代: 我们引入一个队列,这是把递归程序改写成迭代程序的常用方法。初始化时我们把根节点入队两次。每次提取两个结点并比较它们的值(队列中每两个连续的结点应该是相等的,而且它们的子树互为镜像),然后将两个结点的左右子结点按相反的顺序插入队列中。当队列为空时,或者我们检测到树不对称(即从队列中取出两个不相等的连续结点)时,该算法结束。

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean isSymmetric(TreeNode root) {return check(root, root);}private boolean check(TreeNode rootLeft, TreeNode rootRight) {Queue<TreeNode> q = new LinkedList<TreeNode>();q.offer(rootLeft);q.offer(rootRight);while(!q.isEmpty()) {rootLeft = q.poll();rootRight = q.poll();if (rootLeft == null && rootRight == null) {continue;}if ((rootLeft == null || rootRight == null) || (rootLeft.val != rootRight.val)) {return false;}q.offer(rootLeft.left);q.offer(rootRight.right);q.offer(rootLeft.right);q.offer(rootRight.left);}return true;}
}

时间复杂度: 这里遍历了这棵树,渐进时间复杂度为O(n)
空间复杂度: 这里需要用一个队列来维护节点,每个节点最多进队一次,出队一次,队列中最多不会超过n个点,故渐进空间复杂度为O(n)

【3】对称二叉树定义: 对于树中 任意两个对称节点LR,一定有:
L.val = R.val :即此两对称节点值相等。
L.left.val = R.right.val :即L的 左子节点 和R的 右子节点 对称。
L.right.val = R.left.val :即L的 右子节点 和R的 左子节点 对称。
根据以上规律,考虑从顶至底递归,判断每对左右节点是否对称,从而判断树是否为对称二叉树。

算法流程: 函数isSymmetric(root)
【1】特例处理: 若根节点 root 为空,则直接返回 truetruetrue 。
【2】返回值: 即 recur(root.left, root.right) ;

函数recur(L, R)
终止条件:
1、当 L 和 R 同时越过叶节点: 此树从顶至底的节点都对称,因此返回 truetruetrue 。
2、当 L 或 R 中只有一个越过叶节点: 此树不对称,因此返回 falsefalsefalse 。
3、当节点 L 值 ≠ 节点 R 值: 此树不对称,因此返回 falsefalsefalse 。

递推工作:
1、判断两节点 L.left 和 R.right 是否对称,即 recur(L.left, R.right) 。
2、判断两节点 L.right 和 R.left 是否对称,即 recur(L.right, R.left) 。
3、返回值: 两对节点都对称时,才是对称树,因此用与逻辑符 && 连接。
在这里插入图片描述

class Solution {public boolean isSymmetric(TreeNode root) {return root == null || recur(root.left, root.right);}boolean recur(TreeNode L, TreeNode R) {if (L == null && R == null) return true;if (L == null || R == null || L.val != R.val) return false;return recur(L.left, R.right) && recur(L.right, R.left);}
}

复杂度分析:
时间复杂度O(N) 其中N为二叉树的节点数量,每次执行recur()可以判断一对节点是否对称,因此最多调用N/2recur()方法。
空间复杂度O(N) 如下图所示,最差情况下(二叉树退化为链表),系统使用O(N)大小的空间。
在这里插入图片描述

相关文章:

对称二叉树[简单]

优质博文&#xff1a;IT-BLOG-CN 一、题目 给你一个二叉树的根节点root&#xff0c; 检查它是否轴对称。 示例 1&#xff1a; 输入&#xff1a;root [1,2,2,3,4,4,3] 输出&#xff1a;true 示例 2&#xff1a; 输入&#xff1a;root [1,2,2,null,3,null,3] 输出&#xf…...

判断GIF类型并使用ImageDecoder解析GIF图

一、判断是否为GIF图片类型 在JavaScript中&#xff0c;判断用户上传的文件是否为GIF文件类型时&#xff0c;通常可以通过检查文件的type属性或文件的拓展名来判断&#xff0c;但是由于文件拓展名可以轻易被用户修改&#xff0c;type属性是由浏览器根据文件拓展名猜测得出的&a…...

数组对象数据修改后页面没有更新,无法进行编辑,校验失效问题

在 Vue 中&#xff0c;当你通过 Object.assign 或其他方式修改了对象中的某个属性时&#xff0c;Vue 并不会触发组件重新渲染&#xff0c;因此表单中的 input 框无法及时更新。这可能导致在修改表单数据后&#xff0c;页面没有更新&#xff0c;而且表单校验也失效的情况。这是因…...

什么是低代码?有什么特点?

低代码是一种高效的软件开发方法&#xff0c;它允许开发者通过图形化界面和预构建的代码块&#xff0c;以最小化传统手写代码的方式快速构建应用程序。这种方法旨在加速应用程序的开发周期&#xff0c;同时降低技术门槛和成本。以下是根据驰骋低代码设计者的观念与主张&#xf…...

Kafka 消息保留时长由 24 小时变更为 72 小时的影响分析

目录 Kafka 消息保留时长由 24 小时变更为 72 小时的影响分析Kafka 消息存储机制保留时长对生产速度的影响保留时长对消费速度的影响底层分析与优化建议附加&#xff1a;将 Kafka 消息保留时长从 24 小时更改为 72 小时后&#xff0c;CPU 使用率从 40% 上升到 70% 的现象1. 增加…...

MySQL A表的字段值更新为B表的字段值

MySQL A表的字段值更新为B表的字段值 准备数据表 create table person (id int unsigned auto_increment comment 主键 primary key,uuid varchar(32) not null comment 系统唯一标识符32个长度的字符串,mobile varchar(11) null comment 中国国内手机号,nickn…...

TCP 建链(三次握手)和断链(四次握手)

TCP 建链&#xff08;三次握手&#xff09;和断链&#xff08;四次挥手&#xff09; 背景简介建链&#xff08;三次握手&#xff09;断链&#xff08;四次挥手&#xff09;序号及标志位延伸问题为什么建立连接需要握手三次&#xff0c;两次行不行&#xff1f;三次握手可以携带数…...

SpringBoot集成JOOQ加Mybatis-plus使用@Slf4j日志

遇到个问题记录下&#xff0c;就是SpringBoot使用Mybatis和Mybatis-plus时可以正常打印日志&#xff0c;但是JOOQ的操作日志确打印不出来&#xff1f; 下面的解决方法就是将JOOQ的日志单独配置出来&#xff0c;直接给你们配置吧&#xff01; 在项目的resources目录下创建日志…...

浅谈JavaScript中的对象赋值

目录 常见的对象赋值方式 直接赋值和对象扩展&#xff08;浅拷贝&#xff09;两种赋值方式区别 区别 联系 常见的对象赋值方式 1. 直接赋值&#xff1a;this.info this.deviceInfo&#xff0c;将一个对象的引用赋给另一个变量&#xff0c;它们引用同一个对象。 2. 对象扩…...

Java面试题-集合

Java面试题-集合 1、什么是集合&#xff1f;2、集合和数组的区别是什么&#xff1f;3、集合有哪些特点&#xff1f;4、常用的集合类有哪些&#xff1f;5、List&#xff0c; Set&#xff0c; Map三者的区别&#xff1f;6、说说集合框架底层数据结构&#xff1f;7、线程安全的集合…...

从当当网批量获取图书信息

爬取当当网图书数据并保存到本地&#xff0c;使用request、lxml的etree模块、pandas保存数据为excel到本地。 爬取网页的url为&#xff1a; http://search.dangdang.com/?key{}&actinput&page_index{} 其中key为搜索关键字&#xff0c;page_index为页码。 爬取的数据…...

python爬虫之JS逆向——网页数据解析

目录 一、正则 1 正则基础 元字符 基本使用 通配符: . 字符集: [] 重复 位置 管道符和括号 转义符 转义功能 转义元字符 2 正则进阶 元字符组合(常用) 模式修正符 re模块的方法 有名分组 compile编译 二、bs4 1 四种对象 2 导航文档树 嵌套选择 子节点、…...

VL53L4CX TOF开发(2)----修改测距范围及测量频率

VL53L4CX TOF开发.2--修改测距范围及测量频率 概述视频教学样品申请完整代码下载测距范围测量频率硬件准备技术规格系统框图应用示意图生成STM32CUBEMX选择MCU串口配置IIC配置 XSHUTGPIO1X-CUBE-TOF1app_tof.c详细解释测量频率修改修改测距范围 概述 最近在弄ST和瑞萨RA的课程…...

C++之noexcept

目录 1.概述 2.noexcept作为说明符 3.noexcept作为运算符 4.传统throw与noexcept比较 5.原理剖析 6.总结 1.概述 在C中&#xff0c;noexcept是一个关键字&#xff0c;用于指定函数不会抛出异常。如果函数保证不会抛出异常&#xff0c;编译器可以进行更多优化&#xff0c;…...

Kafka之Broker原理

1. 日志数据的存储 1.1 Partition 1. 为了实现横向扩展&#xff0c;把不同的数据存放在不同的 Broker 上&#xff0c;同时降低单台服务器的访问压力&#xff0c;我们把一个Topic 中的数据分隔成多个 Partition 2. 每个 Partition 中的消息是有序的&#xff0c;顺序写入&#x…...

RabbitMQ docker安装及使用

1. docker安装RabbitMQ docker下载及配置环境 docker pull rabbitmq:management # 创建用于挂载的目录 mkdir -p /home/docker/rabbitmq/{data,conf,log} # 创建完成之后要对所创建文件授权权限&#xff0c;都设置成777 否则在启动容器的时候容易失败 chmod -R 777 /home/doc…...

篇3:Mapbox Style Specification

接《篇2:Mapbox Style Specification》,继续解读Mapbox Style Specification。 目录 Spec Reference Root 附录: MapBox Terrain-RGB...

C#WPF数字大屏项目实战11--质量控制

1、区域划分 2、区域布局 3、视图模型 4、控件绑定 5、运行效果 走过路过&#xff0c;不要错过&#xff0c;欢迎点赞&#xff0c;收藏&#xff0c;转载&#xff0c;复制&#xff0c;抄袭&#xff0c;留言&#xff0c;动动你的金手指&#xff0c;财务自由...

第九十七节 Java面向对象设计 - Java Object.Finalize方法

Java面向对象设计 - Java Object.Finalize方法 Java提供了一种在对象即将被销毁时执行资源释放的方法。 在Java中&#xff0c;我们创建对象&#xff0c;但是我们不能销毁对象。 JVM运行一个称为垃圾收集器的低优先级特殊任务来销毁不再引用的所有对象。 垃圾回收器给我们一个…...

【scikit-learn009】异常检测系列:单类支持向量机(OC-SVM)实战总结(看这篇就够了,已更新)

1.一直以来想写下机器学习训练AI算法的系列文章,作为较火的机器学习框架,也是日常项目开发中常用的一款工具,最近刚好挤时间梳理、总结下这块儿的知识体系。 2.熟悉、梳理、总结下scikit-learn框架OCSVM模型相关知识体系。 3.欢迎批评指正,欢迎互三,跪谢一键三连! 4.欢迎…...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

重启Eureka集群中的节点,对已经注册的服务有什么影响

先看答案&#xff0c;如果正确地操作&#xff0c;重启Eureka集群中的节点&#xff0c;对已经注册的服务影响非常小&#xff0c;甚至可以做到无感知。 但如果操作不当&#xff0c;可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

JavaScript基础-API 和 Web API

在学习JavaScript的过程中&#xff0c;理解API&#xff08;应用程序接口&#xff09;和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能&#xff0c;使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...

纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...

【JVM】Java虚拟机(二)——垃圾回收

目录 一、如何判断对象可以回收 &#xff08;一&#xff09;引用计数法 &#xff08;二&#xff09;可达性分析算法 二、垃圾回收算法 &#xff08;一&#xff09;标记清除 &#xff08;二&#xff09;标记整理 &#xff08;三&#xff09;复制 &#xff08;四&#xff…...

Kubernetes 网络模型深度解析:Pod IP 与 Service 的负载均衡机制,Service到底是什么?

Pod IP 的本质与特性 Pod IP 的定位 纯端点地址&#xff1a;Pod IP 是分配给 Pod 网络命名空间的真实 IP 地址&#xff08;如 10.244.1.2&#xff09;无特殊名称&#xff1a;在 Kubernetes 中&#xff0c;它通常被称为 “Pod IP” 或 “容器 IP”生命周期&#xff1a;与 Pod …...

十九、【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建

【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建 前言准备工作第一部分:回顾 Django 内置的 `User` 模型第二部分:设计并创建 `Role` 和 `UserProfile` 模型第三部分:创建 Serializers第四部分:创建 ViewSets第五部分:注册 API 路由第六部分:后端初步测…...

vue3 daterange正则踩坑

<el-form-item label"空置时间" prop"vacantTime"> <el-date-picker v-model"form.vacantTime" type"daterange" start-placeholder"开始日期" end-placeholder"结束日期" clearable :editable"fal…...

comfyui 工作流中 图生视频 如何增加视频的长度到5秒

comfyUI 工作流怎么可以生成更长的视频。除了硬件显存要求之外还有别的方法吗&#xff1f; 在ComfyUI中实现图生视频并延长到5秒&#xff0c;需要结合多个扩展和技巧。以下是完整解决方案&#xff1a; 核心工作流配置&#xff08;24fps下5秒120帧&#xff09; #mermaid-svg-yP…...

保姆级【快数学会Android端“动画“】+ 实现补间动画和逐帧动画!!!

目录 补间动画 1.创建资源文件夹 2.设置文件夹类型 3.创建.xml文件 4.样式设计 5.动画设置 6.动画的实现 内容拓展 7.在原基础上继续添加.xml文件 8.xml代码编写 (1)rotate_anim (2)scale_anim (3)translate_anim 9.MainActivity.java代码汇总 10.效果展示 逐帧…...