剑指 Offer 28. 对称的二叉树
剑指 Offer 28. 对称的二叉树
难度:easy\color{Green}{easy}easy
题目描述
请实现一个函数,用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样,那么它是对称的。
例如,二叉树 [1,2,2,3,4,4,3] 是对称的。
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
示例 1:
输入:root = [1,2,2,3,4,4,3]
输出:true
示例 2:
输入:root = [1,2,2,null,3,null,3]
输出:false
限制:
0<=节点个数<=10000 <= 节点个数 <= 10000<=节点个数<=1000
注意:本题与主站 101 题相同:https://leetcode-cn.com/problems/symmetric-tree/
算法
(递归)
对称二叉树定义:
-
对于树中 任意两个对称节点 L 和 R ,一定有:
- L.val=R.val :即此两对称节点值相等。
- L.left.val=R.right.val :即 L 的 左子节点 和 R 的 右子节点 对称;
- L.right.val=R.left.val :即 L 的 右子节点 和 R 的 左子节点 对称。
-
根据以上规律,考虑从顶至底递归,判断每对节点是否对称,从而判断树是否为对称二叉树。
mirrTree(TreeNode* a, TreeNode* b)
终止条件:
- 当 L 和 R 有一个为空的时候: 判断如果此时都为空,返回 true,否则返回 false;
递推工作:
- 判断两节点 L.left 和 R.right 是否对称,即 mirrTree(L.left, R.right) ;
- 判断两节点 L.right 和 R.left 是否对称,即 mirrTree(L.right, R.left) ;
返回值: 两对节点都对称时,才是对称树,因此用与逻辑符 && 连接。
isSymmetric(root) :
- 特例处理: 若根节点 root 为空,则直接返回 true 。
- 返回值: 即 mirrTree(root.left, root.right) ;
复杂度分析
-
时间复杂度:O(n)O(n)O(n),其中 nnn 是二叉树的节点数量。
-
空间复杂度 : 最差情况下(见下图),二叉树退化为链表,系统使用 O(n)O(n)O(n) 大小的栈空间。
C++ 代码
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:bool isSymmetric(TreeNode* root) {if (!root) return true;return mirrTree(root->left, root->right);}bool mirrTree(TreeNode* a, TreeNode* b) {if (!a || !b) return !a && !b;if (a->val != b->val) return false;return mirrTree(a->left, b->right) && mirrTree(a->right, b->left);}
};
相关文章:

剑指 Offer 28. 对称的二叉树
剑指 Offer 28. 对称的二叉树 难度:easy\color{Green}{easy}easy 题目描述 请实现一个函数,用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样,那么它是对称的。 例如,二叉树 [1,2,2,3,4,4,3] 是对称的。 但是下…...

深入Spring底层透析后置处理器之豁然开朗篇
目录前言Spring的后置处理器Bean工厂后置处理器Bean后置处理器自定义Component实现注解开发前言 看这篇文章之前,需要了解Bean创建的过程,本篇文章是接着bean创建的基本流程的续写 Bean创建的基本过程:http://t.csdn.cn/1lK2d Spring的后置处…...

软件测试(基础定义篇)
测试基础 1、什么是软件测试?2、常见的测试分类3、质量模型 4、软件测试流程 5、测试用例 6、测试用例设计方法 )1、什么是软件测试? 1、什么是软件? 答:软件是控制计算机硬件工作的工具。 2、软件的组成? 3、什么是…...
华为OD机试 - 寻找目标字符串 | 机试题算法思路 【2023】
最近更新的博客 华为OD机试 - 简易压缩算法(Python) | 机试题算法思路 【2023】 华为OD机试题 - 获取最大软件版本号(JavaScript) 华为OD机试 - 猜字谜(Python) | 机试题+算法思路 【2023】 华为OD机试 - 删除指定目录(Python) | 机试题算法思路 【2023】 华为OD机试 …...

使用echart绘制中国地图并显示人数
文章目录引言效果如图所示vue中echarts4.9版本,地图的使用引言 在做毕设的过程中,有一个需求:根据用户的ip,在前端展示出中国地图,然后展现出每个省有多少人这样子 经过百度后,发现可以使用echart来完成该…...

Git的常用命令
1:软件安装1.1:Git下载与安装百度上搜索Git官网:https://git-scm.com/下载:https://git-scm.com/download/win下载Git安装程序,双击安装 Git-2.9.3.2-64-bit.exe配置环境变量path 使用git --version查看 git 是否安装成…...
AcWing1018.最低通行费
1018.最低通行费一个商人穿过一个 NN 的正方形的网格,去参加一个非常重要的商务活动。他要从网格的左上角进,右下角出。每穿越中间 1 个小方格,都要花费 1 个单位时间。商人必须在 (2N−1)(2−1) 个单位时间穿越出去。而在经过中间的每个小方…...

【面试题】vue中的插槽是什么?
大厂面试题分享 面试题库后端面试题库 (面试必备) 推荐:★★★★★地址:前端面试题库一、slot是什么在HTML中 slot 元素 ,作为 Web Components 技术套件的一部分,是Web组件内的一个占位符该占位符可以在后期…...
Go语言结构体struct详解,Go空结构体的这些妙用你知道吗?
本文详解了Go语言结构体的各个知识点,最后介绍了空结构体的3种妙用。希望对你有帮助。 定义 结构体,是一种自定义的数据类型,由多个数据类型组合而成。用于描述一类事物相关属性。 定义方式: type 类型名 struct {字段名 字段类…...
华为OD机试 - 航天器(Python) | 机试题+算法思路+考点+代码解析 【2023】
航天器 题目 给航天器一侧加装长方形和正方形的太阳能板(图中的斜线区域); 需要先安装两个支柱(图中的黑色竖条); 再在支柱的中间部分固定太阳能板; 但航天器不同位置的支柱长度不同; 太阳能板的安装面积受限于最短一侧的那支支柱的长度; 现提供一组整型数组的支柱高度数据;…...

【Optional】告别丑陋判空,使用Optional类
一、概述 当项目中充斥着大量的、丑陋的判空语句,如下: if (user ! null) {Address address user.getAddress();if (address ! null) {Country country address.getCountry();if (country ! null) {String isocode country.getIsocode();if (isocod…...

魔兽世界服务端端新手搭建教程
明杰也是很久以前开始研究魔兽服务器架设,主要原因是亚服经常要排队6-7个小时,去不排除的服和单机没啥区别,以怀旧服玩到10级以后就开始玩335端,一开始也和新入手的人一样云里雾里的,经过长时间的学习总算有点成就,向新…...

宝塔搭建实战人才求职管理系统mobile手机端vue源码(五)
大家好啊,我是测评君,欢迎来到web测评。 上一期给大家分享骑士cms会员管理member前端vue在本地运行打包、宝塔发布部署的方式,本期给大家分享,mobile移动端vue怎么在本地运行,打包,实现线上功能更新替换的方…...
生态应用:探讨 NGINX 与上下游系统集成时的开发经验
NGINX 作为一款高性能的 Web 服务器和反向代理服务器,在各种应用场景中广泛应用。随着业务的发展,我们在使用 NGINX 时,可能需要将其与其他系统进行集成,以实现更加复杂的业务需求。 本文将结合实际应用场景,探讨 NGI…...

ArcGIS批量拼接大量栅格遥感影像:Mosaic工具
本文介绍在ArcGIS下属的ArcMap软件中,基于Mosaic工具,批量对大量栅格遥感影像文件加以拼接、镶嵌的方法。 在GIS应用中,我们时常需要对大量栅格遥感影像数据加以批量拼接的工作。这一步骤可以基于Python语言实现,具体可以参考文章…...
Flink UI部署jar包报错
错误描述: 通过Flink的UI中的Submit New Job菜单添加jar包的时候提示报错。报错信息的关键字是“The LocalStreamEnvironment cannot be used when submitting a program through a client, or running in a TestEnvironment context”,最关键的是“Loc…...
Linux就该这么学:RAID与LVM磁盘阵列技术
这里写目录标题 7.1.1 部署磁盘阵列7.1.2 损坏磁盘阵列及修复7.1.3 磁盘阵列+备份盘7.1.4 删除磁盘阵列1. 需要将所有的磁盘都设置成停用状态:2. 逐一移除出去3. 续停用整个RAID磁盘阵列7.2 LVM逻辑卷管理器7.2.1 部署逻辑卷7.2.2 扩容逻辑卷7.2.3 缩小逻辑卷7.2.4 逻辑卷快照…...

Prometheus+Grafana监控
1、简介1.1 Prometheus官网地址:https://prometheus.io/Prometheus是一个开源的监控系统,起源于SoundCloud。它由以下几个核心组件构成:数据爬虫: 根据配置的时间定期的通过HTTP抓去metrics数据。time-series 数据库: …...
【JUC2022】第三章 线程中断与 LockSupport
【JUC2022】第三章 线程中断与 LockSupport 文章目录【JUC2022】第三章 线程中断与 LockSupport一、线程中断1.什么是中断机制2.中断 API3.代码实现4.Thread.sleep()二、LockSupport1.什么是 LockSupport2.代码实现3.总结一、线程中断 1.什么是中断机制 首先,一个…...
数据结构刷题(七):202快乐数、1两数之和、454四数相加II、15三数之和、18四树之和
1.快乐数题目链接思路:使用set,当set中出现相同元素时,返回false注意:while循环中语句顺序; 除数取余。解法:public boolean isHappy(int n){Set<Integer> res new HashSet<>();int[] arr ne…...
后进先出(LIFO)详解
LIFO 是 Last In, First Out 的缩写,中文译为后进先出。这是一种数据结构的工作原则,类似于一摞盘子或一叠书本: 最后放进去的元素最先出来 -想象往筒状容器里放盘子: (1)你放进的最后一个盘子(…...

Cinnamon修改面板小工具图标
Cinnamon开始菜单-CSDN博客 设置模块都是做好的,比GNOME简单得多! 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...
爬虫基础学习day2
# 爬虫设计领域 工商:企查查、天眼查短视频:抖音、快手、西瓜 ---> 飞瓜电商:京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空:抓取所有航空公司价格 ---> 去哪儿自媒体:采集自媒体数据进…...
稳定币的深度剖析与展望
一、引言 在当今数字化浪潮席卷全球的时代,加密货币作为一种新兴的金融现象,正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而,加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下,稳定…...
基于鸿蒙(HarmonyOS5)的打车小程序
1. 开发环境准备 安装DevEco Studio (鸿蒙官方IDE)配置HarmonyOS SDK申请开发者账号和必要的API密钥 2. 项目结构设计 ├── entry │ ├── src │ │ ├── main │ │ │ ├── ets │ │ │ │ ├── pages │ │ │ │ │ ├── H…...

消防一体化安全管控平台:构建消防“一张图”和APP统一管理
在城市的某个角落,一场突如其来的火灾打破了平静。熊熊烈火迅速蔓延,滚滚浓烟弥漫开来,周围群众的生命财产安全受到严重威胁。就在这千钧一发之际,消防救援队伍迅速行动,而豪越科技消防一体化安全管控平台构建的消防“…...

jdbc查询mysql数据库时,出现id顺序错误的情况
我在repository中的查询语句如下所示,即传入一个List<intager>的数据,返回这些id的问题列表。但是由于数据库查询时ID列表的顺序与预期不一致,会导致返回的id是从小到大排列的,但我不希望这样。 Query("SELECT NEW com…...

goreplay
1.github地址 https://github.com/buger/goreplay 2.简单介绍 GoReplay 是一个开源的网络监控工具,可以记录用户的实时流量并将其用于镜像、负载测试、监控和详细分析。 3.出现背景 随着应用程序的增长,测试它所需的工作量也会呈指数级增长。GoRepl…...
写一个shell脚本,把局域网内,把能ping通的IP和不能ping通的IP分类,并保存到两个文本文件里
写一个shell脚本,把局域网内,把能ping通的IP和不能ping通的IP分类,并保存到两个文本文件里 脚本1 #!/bin/bash #定义变量 ip10.1.1 #循环去ping主机的IP for ((i1;i<10;i)) doping -c1 $ip.$i &>/dev/null[ $? -eq 0 ] &&am…...