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

剑指 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. 对称的二叉树 难度&#xff1a;easy\color{Green}{easy}easy 题目描述 请实现一个函数&#xff0c;用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样&#xff0c;那么它是对称的。 例如&#xff0c;二叉树 [1,2,2,3,4,4,3] 是对称的。 但是下…...

深入Spring底层透析后置处理器之豁然开朗篇

目录前言Spring的后置处理器Bean工厂后置处理器Bean后置处理器自定义Component实现注解开发前言 看这篇文章之前&#xff0c;需要了解Bean创建的过程&#xff0c;本篇文章是接着bean创建的基本流程的续写 Bean创建的基本过程&#xff1a;http://t.csdn.cn/1lK2d Spring的后置处…...

软件测试(基础定义篇)

测试基础 1、什么是软件测试&#xff1f;2、常见的测试分类3、质量模型 4、软件测试流程 5、测试用例 6、测试用例设计方法 )1、什么是软件测试&#xff1f; 1、什么是软件&#xff1f; 答&#xff1a;软件是控制计算机硬件工作的工具。 2、软件的组成&#xff1f; 3、什么是…...

华为OD机试 - 寻找目标字符串 | 机试题算法思路 【2023】

最近更新的博客 华为OD机试 - 简易压缩算法(Python) | 机试题算法思路 【2023】 华为OD机试题 - 获取最大软件版本号(JavaScript) 华为OD机试 - 猜字谜(Python) | 机试题+算法思路 【2023】 华为OD机试 - 删除指定目录(Python) | 机试题算法思路 【2023】 华为OD机试 …...

使用echart绘制中国地图并显示人数

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

Git的常用命令

1&#xff1a;软件安装1.1&#xff1a;Git下载与安装百度上搜索Git官网&#xff1a;https://git-scm.com/下载&#xff1a;https://git-scm.com/download/win下载Git安装程序&#xff0c;双击安装 Git-2.9.3.2-64-bit.exe配置环境变量path 使用git --version查看 git 是否安装成…...

AcWing1018.最低通行费

1018.最低通行费一个商人穿过一个 NN 的正方形的网格&#xff0c;去参加一个非常重要的商务活动。他要从网格的左上角进&#xff0c;右下角出。每穿越中间 1 个小方格&#xff0c;都要花费 1 个单位时间。商人必须在 (2N−1)(2−1) 个单位时间穿越出去。而在经过中间的每个小方…...

【面试题】vue中的插槽是什么?

大厂面试题分享 面试题库后端面试题库 &#xff08;面试必备&#xff09; 推荐&#xff1a;★★★★★地址&#xff1a;前端面试题库一、slot是什么在HTML中 slot 元素 &#xff0c;作为 Web Components 技术套件的一部分&#xff0c;是Web组件内的一个占位符该占位符可以在后期…...

Go语言结构体struct详解,Go空结构体的这些妙用你知道吗?

本文详解了Go语言结构体的各个知识点&#xff0c;最后介绍了空结构体的3种妙用。希望对你有帮助。 定义 结构体&#xff0c;是一种自定义的数据类型&#xff0c;由多个数据类型组合而成。用于描述一类事物相关属性。 定义方式&#xff1a; type 类型名 struct {字段名 字段类…...

华为OD机试 - 航天器(Python) | 机试题+算法思路+考点+代码解析 【2023】

航天器 题目 给航天器一侧加装长方形和正方形的太阳能板(图中的斜线区域); 需要先安装两个支柱(图中的黑色竖条); 再在支柱的中间部分固定太阳能板; 但航天器不同位置的支柱长度不同; 太阳能板的安装面积受限于最短一侧的那支支柱的长度; 现提供一组整型数组的支柱高度数据;…...

【Optional】告别丑陋判空,使用Optional类

一、概述 当项目中充斥着大量的、丑陋的判空语句&#xff0c;如下&#xff1a; if (user ! null) {Address address user.getAddress();if (address ! null) {Country country address.getCountry();if (country ! null) {String isocode country.getIsocode();if (isocod…...

魔兽世界服务端端新手搭建教程

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

宝塔搭建实战人才求职管理系统mobile手机端vue源码(五)

大家好啊&#xff0c;我是测评君&#xff0c;欢迎来到web测评。 上一期给大家分享骑士cms会员管理member前端vue在本地运行打包、宝塔发布部署的方式&#xff0c;本期给大家分享&#xff0c;mobile移动端vue怎么在本地运行&#xff0c;打包&#xff0c;实现线上功能更新替换的方…...

生态应用:探讨 NGINX 与上下游系统集成时的开发经验

NGINX 作为一款高性能的 Web 服务器和反向代理服务器&#xff0c;在各种应用场景中广泛应用。随着业务的发展&#xff0c;我们在使用 NGINX 时&#xff0c;可能需要将其与其他系统进行集成&#xff0c;以实现更加复杂的业务需求。 本文将结合实际应用场景&#xff0c;探讨 NGI…...

ArcGIS批量拼接大量栅格遥感影像:Mosaic工具

本文介绍在ArcGIS下属的ArcMap软件中&#xff0c;基于Mosaic工具&#xff0c;批量对大量栅格遥感影像文件加以拼接、镶嵌的方法。 在GIS应用中&#xff0c;我们时常需要对大量栅格遥感影像数据加以批量拼接的工作。这一步骤可以基于Python语言实现&#xff0c;具体可以参考文章…...

Flink UI部署jar包报错

错误描述&#xff1a; 通过Flink的UI中的Submit New Job菜单添加jar包的时候提示报错。报错信息的关键字是“The LocalStreamEnvironment cannot be used when submitting a program through a client, or running in a TestEnvironment context”&#xff0c;最关键的是“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官网地址&#xff1a;https://prometheus.io/Prometheus是一个开源的监控系统&#xff0c;起源于SoundCloud。它由以下几个核心组件构成&#xff1a;数据爬虫&#xff1a; 根据配置的时间定期的通过HTTP抓去metrics数据。time-series 数据库&#xff1a; …...

【JUC2022】第三章 线程中断与 LockSupport

【JUC2022】第三章 线程中断与 LockSupport 文章目录【JUC2022】第三章 线程中断与 LockSupport一、线程中断1.什么是中断机制2.中断 API3.代码实现4.Thread.sleep()二、LockSupport1.什么是 LockSupport2.代码实现3.总结一、线程中断 1.什么是中断机制 首先&#xff0c;一个…...

数据结构刷题(七):202快乐数、1两数之和、454四数相加II、15三数之和、18四树之和

1.快乐数题目链接思路&#xff1a;使用set&#xff0c;当set中出现相同元素时&#xff0c;返回false注意&#xff1a;while循环中语句顺序&#xff1b; 除数取余。解法&#xff1a;public boolean isHappy(int n){Set<Integer> res new HashSet<>();int[] arr ne…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的&#xff0c;比GNOME简单得多&#xff01; 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代&#xff0c;加密货币作为一种新兴的金融现象&#xff0c;正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而&#xff0c;加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下&#xff0c;稳定…...

基于鸿蒙(HarmonyOS5)的打车小程序

1. 开发环境准备 安装DevEco Studio (鸿蒙官方IDE)配置HarmonyOS SDK申请开发者账号和必要的API密钥 2. 项目结构设计 ├── entry │ ├── src │ │ ├── main │ │ │ ├── ets │ │ │ │ ├── pages │ │ │ │ │ ├── H…...

消防一体化安全管控平台:构建消防“一张图”和APP统一管理

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

jdbc查询mysql数据库时,出现id顺序错误的情况

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

goreplay

1.github地址 https://github.com/buger/goreplay 2.简单介绍 GoReplay 是一个开源的网络监控工具&#xff0c;可以记录用户的实时流量并将其用于镜像、负载测试、监控和详细分析。 3.出现背景 随着应用程序的增长&#xff0c;测试它所需的工作量也会呈指数级增长。GoRepl…...

写一个shell脚本,把局域网内,把能ping通的IP和不能ping通的IP分类,并保存到两个文本文件里

写一个shell脚本&#xff0c;把局域网内&#xff0c;把能ping通的IP和不能ping通的IP分类&#xff0c;并保存到两个文本文件里 脚本1 #!/bin/bash #定义变量 ip10.1.1 #循环去ping主机的IP for ((i1;i<10;i)) doping -c1 $ip.$i &>/dev/null[ $? -eq 0 ] &&am…...