(树) 剑指 Offer 28. 对称的二叉树 ——【Leetcode每日一题】

news/2024/3/4 9:19:28

❓ 剑指 Offer 28. 对称的二叉树

难度:简单

请实现一个函数,用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样,那么它是对称的。

例如,二叉树 [1,2,2,3,4,4,3] 是对称的。

    1/ \2   2/ \ / \3  4 4  3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

    1/ \2   2\   \3    3

示例 1:

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

示例 2:

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

限制

  • 0 <= 节点个数 <= 1000

注意:本题与 101. 对称二叉树 相同。

💡思路:

法一:递归

如果一个树的左子树与右子树镜像对称,那么这个树是对称的:

  • 每次检查当前 root1root2 节点的值是否 相等;
  • 如果 相等 再判断左右子树是否对称:
    • root1左子树 对应 root2右子树
    • root1右子树 对应 root2左子树
    • 同时成立时返回 true

法二:迭代

方法一 中我们用 递归 的方法实现了对称性的判断,那么如何用迭代的方法实现呢?

  • 要引入一个 队列 q,这是把递归程序改写成迭代程序的常用方法。

如果 root 不为空,将左右子树根节点分别加入队列:

  • 只要队列不为空,每次从队列中提取两个结点并比较它们的值(队列中每两个连续的结点应该是相等的,而且它们的子树互为镜像);
  • 然后将两个结点的左右子树按相反的顺序插入队列中;
    • 插入 temp1 的左子树后,紧接着插入 temp2 的右子树的根节点;
    • 然后再插入 temp1 的右子树后,紧接着插入 temp2 的左子树的根节点;
  • 当队列为空时,或者我们检测到树不对称(即从队列中取出两个不相等的连续结点)时,该算法结束。

🍁代码:(C++、Java)

法一:递归
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 {
private:bool isSymTree(TreeNode* root1, TreeNode* root2){if(root1 == nullptr && root2 == nullptr) return true;if(root1 == nullptr || root2 == nullptr || (root1->val != root2->val)) return false;return isSymTree(root1->left, root2->right) && isSymTree(root1->right, root2->left);}
public:bool isSymmetric(TreeNode* root) {if(root == nullptr) return true;return isSymTree(root->left, root->right);}
};

Java

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {private boolean isSymTree(TreeNode root1, TreeNode root2){if(root1 == null && root2 == null) return true;if(root1 == null || root2 == null || (root1.val != root2.val)) return false;return isSymTree(root1.left, root2.right) && isSymTree(root1.right, root2.left);}public boolean isSymmetric(TreeNode root) {if(root == null) return true;return isSymTree(root.left, root.right);} 
}

法二:迭代
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 == nullptr) return true;queue<TreeNode*> q;q.push(root->left);q.push(root->right);while(!q.empty()){TreeNode* temp1 = q.front();q.pop();TreeNode* temp2 = q.front();q.pop();if(temp1 == nullptr && temp2 == nullptr) continue;if(temp1 == nullptr || temp2 == nullptr || (temp1->val != temp2->val)) return false;q.push(temp1->left);q.push(temp2->right);q.push(temp1->right);q.push(temp2->left);}return true;}
};

Java

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

🚀 运行结果:

在这里插入图片描述

🕔 复杂度分析:

  • 时间复杂度 O ( n ) O(n) O(n),其中 nroot 的节点数,遍历了这棵树。
  • 空间复杂度 O ( n ) O(n) O(n)法一 的空间复杂度和递归使用的栈空间有关,这里递归层数不超过 n ; 法二 需要用一个队列来维护节点,每个节点最多进队一次,出队一次,队列中最多不会超过 n 个点。

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!

注: 如有不足,欢迎指正!


http://www.ppmy.cn/news/991831.html

相关文章

搭建自己的Git服务器

环境 服务端&#xff1a;Ubuntu 22.04 客户端&#xff1a;Win11_x64 前提条件&#xff1a;需要确保在Windows机器上能够ping通Ubuntu服务器, 并且服务端与客户端均已安装了Git软件 服务端上的配置操作 以Ubuntu服务器作为Git服务端的运行环境&#xff0c;并方便后期免密推…

Vue2 第九节 过滤器

&#xff08;1&#xff09;定义&#xff1a;对要显示的数据进行特定格式化后再显示 &#xff08;2&#xff09;语法&#xff1a; ① 注册过滤器 1&#xff09;Vue.filter(name, callback) 全局过滤器 2&#xff09; new Vue({filters:{}}) 局部过滤器 ② 使用过滤器 1&…

【C#】并行编程实战:并行编程中的模式

本章将介绍并行编程模式&#xff0c;重点是理解并行代码问题场景并使用并行编程/异步技术解决他们。本章会介绍几种最重要的编程模式。 本教程学习工程&#xff1a;魔术师Dix / HandsOnParallelProgramming GitCode 1、MapReduce 模式 引入 MapReduce 是为了解决处理大数据的问…

web自动化测试,定位不到元素的原因及解决方案

1.动态id定位不到元素 分析原因&#xff1a;每次打开页面&#xff0c;ID都会变化。用ID去找元素&#xff0c;每次刷新页面ID都会发生变化。 解决方案&#xff1a;推荐使用xpath的相对路径方法或者cssSelector查找到该元素。        2.iframe原因定位不到元素 分析原因…

17 反显、修改、提交图书信息功能实战

前言 上节回顾 上一节&#xff0c;我们针对图书列表做了实战练习&#xff0c;主体内容包括顶部的检索区域&#xff0c;中间的el-table数据区域&#xff0c;和底部的el-pagination分页区域&#xff0c;并针对每一块做了讲解&#xff0c;还不太明白上下文的同学可以回过头去看一…

Golang之路---02 基础语法——数组与切片(slice)

数组 数组是一个由固定长度的特定类型元素组成的序列&#xff0c;一个数组可以由零个或多个元素组成。因为数组的长度是固定的。 func main() {//1.声明数组&#xff0c;并给数组的每个元素赋值var arr [3]float32arr[0]1.1arr[1]2.2arr[2]3.3//2.声明并初始化数组//2.1var a…

vue3+ts未使用变量报错的解决

实例 问题原因 tsconfig.json文件中开启了ts语法检查 "strict": true, // 开启严格模式&#xff0c;检查类型声明和赋值...是否合法 "noUnusedLocals": true, // 检查是否存在未使用的变量 "noUnusedParameters": true, // 检查是否存在会使…

AD21原理图的高级应用(五)自定义原理图模板及调用

&#xff08;五&#xff09;自定义原理图模板及调用 1.创建原理图模板2.调用原理图模板 1.创建原理图模板 利用 Altium Designer 软件在原理图中创建自己的模板,可以在图纸的右下角绘制一个表格用于显示图纸的一些参数,例如文件名、作者、修改时间、审核者、公司信息、图纸总数…

一维(1D)CNN模型下轴承故障诊断(Python,TensorFlow框架下,很容易改为其它模型,解压缩后可以直接运行,无需修改任何目录)

1.数据集 使用凯斯西储大学轴承数据集&#xff0c;一共有4种负载下采集的数据&#xff0c;每种负载下有10种 故障状态&#xff1a;三种不同尺寸下的内圈故障、三种不同尺寸下的外圈故障、三种不同尺寸下的滚动体故障和一种正常状态。 2.模型&#xff08;1DCNN&#xff09; 使…

类与对象(上-2)

类与对象&#xff08;上-2&#xff09; 6、类的实例化7、计算类空间的大小8、this指针 6、类的实例化 Test.cpp //用类类型创建对象的过程&#xff0c;称为类的实例化。 //类是对对象进行描述的&#xff0c;是一个 模型 一样的东西&#xff0c;来限定了类有哪些成员&#xff…

一文搞懂mysql(安装、基础命令、存储文件)

1、安装 除此之外&#xff0c;windows在安装前需要额外补加两个东西 dxwebsetup.exe、 vcredist_x64.exe 这俩随便一搜就能找到 在安装前者时要注意取消勾选bing工具栏 mysql下载链接 2、初始化 管理员身份打开cmd >> "path_to_mysql/bin/msqld.exe" --initi…

二叉树中的深搜

一)计算布尔二叉树的值 2331. 计算布尔二叉树的值 - 力扣&#xff08;LeetCode&#xff09; 1)计算布尔二叉树需要从叶子节点向上进行计算&#xff0c;从下向上进行计算 2)完整二叉树是同时拥有左孩子和右孩子&#xff0c;或者是完全没有右孩子 3)当我只是盯着根节点来看的时候…

.Net Core上传组件_.Net Core图片上传组件_Uploader7.0

一、.Net Core上传组件Uploader7.0简介 1.当前版本v7.0&#xff0c;前端框架丰富升级 2.前端jquery框架封装,cover.js, 腾讯云cos-js-sdk-v5.min.js 3.后端&#xff0c;支持Asp.Net 和 Asp.Net Core 矿建 4.数据传输模式支持&#xff1a;WebScoket 、Ajax、Form 模式上传到…

浏览器访问nginx转发打开oss上的html页面默认是下载,修改为预览

使用阿里云盒OSS上传了html页面&#xff0c;在nginx里配置跳转访问该页面时&#xff0c;在浏览器里直接默认下载了该页面&#xff0c;现在想实现预览功能&#xff0c;只需在nginx里的location里修改消息头的Content-Disposition为inline即可 注意要隐藏头信息proxy_hide_header…

【Linux】网络基础

&#x1f34e;作者&#xff1a;阿润菜菜 &#x1f4d6;专栏&#xff1a;Linux系统网络编程 文章目录 一、协议初识和网络协议分层&#xff08;TCP/IP四层模型&#xff09;认识协议TCP/IP五层&#xff08;或四层&#xff09;模型 二、认识MAC地址和IP地址认识MAC地址认识IP地址认…

罗布乐思Roblox学习笔记

罗布乐思 文章目录 罗布乐思基本操作CFrameGUIModule script呼吸灯商店imageChangetag标签知识答题showTips 基本操作 缩放按shift 等比例缩放 ctrl 双向缩放 复制对象 ctrlD &#xff08;如果选择多个对象&#xff0c;按住ctrl&#xff09; F 聚焦 Workspace ​ Terrain…

使用Express部署Vue项目

使用Express部署Vue项目 目录 1. 背景 2. 配置Vue CLI 1.1 安装nodejs 1.2 创建vue-cli 1.3 创建vue项目 1.4 构建vue项目3. 配置Express 2.1 安装express 2.2 创建项目4. 使用express部署vue项目 1&#xff0c;背景 我们想要做一个前后端分离的课程项目&#xff0c;前端…

数据库选型

影响数据库选择的因素 数据量&#xff1a;是否海量数据&#xff0c;单表数据量太大会考验数据库的性能数据结构&#xff1a;结构化 (每条记录的结构都一样) 还是非结构化的 (不同记录的结构可以不一样)是否宽表&#xff1a;一条记录是 10 个域&#xff0c;还是成百上千个域数据…

Java ~ Collection/Executor ~ DelayQueue【源码】

前言 文章 相关系列&#xff1a;《Java ~ Collection【目录】》&#xff08;持续更新&#xff09;相关系列&#xff1a;《Java ~ Executor【目录】》&#xff08;持续更新&#xff09;相关系列&#xff1a;《Java ~ Collection/Executor ~ DelayQueue【源码】》&#xff08;学…

开心档之CSS !important 规则

CSS !important 规则 CSS !important 规则 CSS是网页中最常用的样式语言&#xff0c;用来改变网页的颜色、字体、布局等等。但是当多个样式规则作用于同一个元素上时&#xff0c;由于优先级的差异&#xff0c;可能会出现样式被覆盖的情况。为了解决这个问题&#xff0c;CSS中提…
最新文章