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

力扣第101题 c++ 递归 迭代 双方法 +注释 ~

题目

101. 对称二叉树

简单

给你一个二叉树的根节点 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. compare()函数是用来判断两个节点是否对称的,其中leftright参数分别代表左右子节点。

  2. 首先我们需要判断leftright是否为空,若其中一个节点为空而另一个不为空,那么这两个节点不对称,返回false。如果两个节点都为空,则认为它们对称,返回true

  3. 如果两个节点的值不相等,则说明它们不对称,返回false

  4. 如果两个节点的值相等,则需要递归判断它们的左右子节点是否对称。具体来说,需要比较左子树的左子节点和右子树的右子节点、左子树的右子节点和右子树的左子节点是否对称,即outside = compare(left->left, right->right)inside = compare(left->right, right->left)

  5. 最后,给出判断结果,即只有当左子树的左子节点和右子树的右子节点、左子树的右子节点和右子树的左子节点都对称时,才可以认为这两个节点对称,返回isSame = outside && inside

  6. isSymmetric()函数是判断整个二叉树是否对称的。如果给定的根节点root为空,则直接返回true。否则,调用compare()函数比较根节点的左右子节点是否对称。

  7. 最后,整个程序返回的是isSymmetric()函数的返回值。

复杂度

        时间复杂度:

                O(n)

        时间复杂度是O(n),其中n为二叉树的节点数,因为我们需要遍历每个节点,每个节点都需要进行一次比较。

        空间复杂度

                O(n)

        空间复杂度也是O(n),因为在递归调用compare()函数时,需要不断开辟新的栈空间来存储递归函数的参数和局部变量,最坏的情况下需要递归到最深层,此时栈空间的大小为O(n)。

c++ 代码

 ​
//复杂简单版
class Solution {
public:// 判断节点是否对称的函数bool compare(TreeNode* left, TreeNode* right) {// 首先排除空节点的情况if (left == NULL && right != NULL) return false;else if (left != NULL && right == NULL) return false;else if (left == NULL && right == NULL) return true;// 排除了空节点,再排除数值不相同的情况else if (left->val != right->val) return false;// 此时就是:左右节点都不为空,且数值相同的情况// 此时才做递归,做下一层的判断bool outside = compare(left->left, right->right);   // 左子树:左、 右子树:右bool inside = compare(left->right, right->left);    // 左子树:右、 右子树:左bool isSame = outside && inside;                    // 左子树:中、 右子树:中 (逻辑处理)return isSame;}// 判断整棵二叉树是否对称的函数bool isSymmetric(TreeNode* root) {if (root == NULL) return true;// 如果根节点不为空,调用compare()函数比较左子节点和右子节点是否对称return compare(root->left, root->right);}
};//精简版
class Solution {
public:// 检查两个节点是否对称的函数bool check(TreeNode *p, TreeNode *q) {// 如果两个节点都为空,视为对称if (!p && !q) return true;// 如果其中一个节点为空,另一个节点非空,视为不对称if (!p || !q) return false;// 检查当前节点的值是否相等,并递归检查左子树和右子树是否对称return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);}// 判断整棵二叉树是否对称的函数bool isSymmetric(TreeNode* root) {// 调用check函数,同时传入相同的根节点,判断左子树和右子树是否对称return check(root, root);}
};

思路和解题方法二(迭代)

  1. 首先检查根节点是否为空,若为空直接返回true。

  2. 创建一个队列que,并将根节点的左子树和右子树头结点依次加入队列。

  3. 进入while循环,判断队列是否为空。如果队列不为空,则继续执行循环体。

  4. 在循环体中,从队列中取出两个节点:leftNode为队列首部的节点,rightNode为队列次首部的节点。

  5. 判断左节点和右节点是否都为空。如果是,说明当前节点属于对称的部分,继续循环。

  6. 如果左节点和右节点有一个为空,或者它们的值不相等,返回false,表示不对称。

  7. 如果左节点和右节点都不为空且值相等,将其左孩子、右孩子按顺序依次加入队列,以备后续判断是否对称。

  8. 循环结束后,返回true,表示二叉树是对称的。

复杂度

        时间复杂度:

                O(n)

时间复杂度为O(n),其中n是二叉树的节点数。

        空间复杂度

                O(n)

使用了一个队列来存储节点,因此,空间复杂度为O(n)。

c++ 代码

class Solution {
public:bool isSymmetric(TreeNode* root) {  // 判断二叉树是否对称的函数,传入根节点rootif (root == NULL) return true;  // 如果根节点为空,返回truequeue<TreeNode*> que;  // 创建一个队列que来存储需要判断的节点que.push(root->left);   // 将左子树头结点加入队列que.push(root->right);  // 将右子树头结点加入队列while (!que.empty()) {  // 当队列不为空时,进行循环TreeNode* leftNode = que.front(); que.pop();  // 取出队列首部的节点leftNodeTreeNode* rightNode = que.front(); que.pop();  // 取出队列次首部的节点rightNodeif (!leftNode && !rightNode) {  // 如果左节点为空、右节点为空,说明是对称的,继续循环continue;}// 左右一个节点不为空,或者都不为空但数值不相同,返回falseif ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {return false;  // 如果左右节点有一个为空或者值不相等,直接返回false,表示当前二叉树不对称}// 加入左节点左孩子、右节点右孩子、左节点右孩子、右节点左孩子que.push(leftNode->left);   // 左节点的左孩子que.push(rightNode->right); // 右节点的右孩子que.push(leftNode->right);  // 左节点的右孩子que.push(rightNode->left);  // 右节点的左孩子}return true; // 当循环结束时,说明整个二叉树都对称,返回true}
};

觉得有用的话可以点点赞,支持一下。

如果愿意的话关注一下。会对你有更多的帮助。

每天都会不定时更新哦  >人<  。

相关文章:

力扣第101题 c++ 递归 迭代 双方法 +注释 ~

题目 101. 对称二叉树 简单 给你一个二叉树的根节点 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] 输出&#xff1a;false提示&a…...

Go:实现SMTP邮件发送订阅功能(包含163邮箱、163企业邮箱、谷歌gmail邮箱)

需求很简单&#xff0c;就是用户输入自己的邮箱后&#xff0c;使用官方邮箱给用户发送替邮件模版 目录 前置邮件模版邮箱开启SMTP服务163邮箱163企业邮箱谷歌gmail邮箱腾讯企业邮箱-失败其他邮箱-未操作 邮件发送核心代码config.yaml配置读取邮件相关配置发送邮件 附录 前置 邮…...

Scala第十六章节

Scala第十六章节 scala总目录 文档资料下载 章节目标 掌握泛型方法, 类, 特质的用法了解泛型上下界相关内容了解协变, 逆变, 非变的用法掌握列表去重排序案例 1. 泛型 泛型的意思是泛指某种具体的数据类型, 在Scala中, 泛型用[数据类型]表示. 在实际开发中, 泛型一般是结合…...

C语言 实现 链 显示 效果 查找 修改 删除

显示所有信息 2023年10月1日的描述:今天放假 2023年10月2日的描述:今天有体育 2023年10月3日的描述:今天有数学 2023年10月4日的描述:今天有语文 2023年10月5日的描述:今天有政治 2023年10月6日的描述:今天交学费 2023年10月7日的描述:今天周末 2023年10月8日的描述:今天给家里…...

CSS基础语法第一天

目录 一、CSS 简介 1.1 CSS简介 1.2 CSS语法 ​1.3 CSS 语法规范 1.4 CSS 代码风格 1.4.1 样式格式书写 1.4.2 样式大小写 ​1.4.3 空格规范 二、CSS 基础选择器 2.1选择器分类 2.2标签选择器 2.3 类选择器 2.4 id选择器 2.5 通配符选择器 三、盒子尺寸和背景色 …...

Leetcode 1492.n的第k个因子

给你两个正整数 n 和 k 。 如果正整数 i 满足 n % i 0 &#xff0c;那么我们就说正整数 i 是整数 n 的因子。 考虑整数 n 的所有因子&#xff0c;将它们 升序排列 。请你返回第 k 个因子。如果 n 的因子数少于 k &#xff0c;请你返回 -1 。 示例 1&#xff1a; 输入&#…...

十一工具箱流量主小程序源码

无授权&#xff0c;去过滤机制版本 看到网上发布的都是要授权的 朋友叫我把他去授权&#xff0c;能用就行 就把过滤去了 这样就不用授权 可以免费使用 白嫖党专属 一切接口可用&#xff0c;无需担心不能用 授权者不关站一直可以用 源码下载&#xff1a;https://download.csdn.…...

10.5汇编语言整理

【汇编语言相关语法】 1.汇编语言的组成部分 1.伪操作&#xff1a;不参与程序的执行&#xff0c;但是用于告诉编译器程序该怎么编译 .text .global .end .if .else .endif .data 2.汇编指令 编译器将一条汇编指令编译成一条机器码&#xff0c;在内存里一条指令占4字节内存&…...

Connect to 127.0.0.1:1080 [/127.0.0.1] failed: Connection refused: connect

报错信息 A problem occurred configuring root project CourseSelection. > Could not resolve all artifacts for configuration :classpath.> Could not resolve com.android.tools.build:gradle:3.6.1.Required by:project :> Could not resolve com.android.tool…...

驱动器类产品的接口EMC拓扑方案

驱动器类产品的接口EMC拓扑方案 1. 概述 本文以高压伺服驱动器和变频器类产品为例&#xff0c;对常用端口滤波拓扑方案进行总结&#xff0c;后续根据不同的应用场景可进行适当删减&#xff0c;希望对大家有帮助。 2. 驱动器验证等级 本文推荐拓扑的实验结果&#xff0c;满足…...

2023最新ICP备案查询系统源码 附教程 Thinkphp框架

2023最新ICP备案查询系统源码 附教程 thinkphp框架 本系统支持网址备案&#xff0c;小程序备案&#xff0c;APP备案查询&#xff0c;快应用备案查询 优势&#xff1a; 响应速度快&#xff0c;没有延迟&#xff0c;没有缓存&#xff0c;数据与官方同步 源码下载&#xff1a;ht…...

大数据Doris(六):编译 Doris遇到的问题

文章目录 编译 Doris遇到的问题 一、js_generator.cc:(.text+0xfc3c): undefined reference to `well_known_types_js’...

vue重修004上部

文章目录 版权声明组件的三大组成部分scoped解决样式冲突scoped原理2.代码演示 组件data函数说明演示 组件通信组件关系分类通信解决方案父子通信流程子向父通信代 props详解props校验props&data、单向数据流 小黑记事本&#xff08;组件版&#xff09;基础组件结构需求和实…...

【C++ techniques】要求/禁止/判断—对象产生于堆中

有时候我们想让某种对象具有“自杀”的能力&#xff0c;所以我们必须要求对象存在堆中&#xff0c;以便我们调用delete this&#xff1b;另一些时候&#xff0c;我们要求拥有某种确定性&#xff0c;保证某一些类型绝不会发生内存泄漏&#xff0c;原因是没有任何一个该类型的对象…...

吃鸡高手亲授:玩转绝地求生,分享顶级游戏干货!

绝地求生&#xff08;PUBG&#xff09;自上线以来&#xff0c;成为了全球热门游戏。作为吃鸡行家&#xff0c;我将分享一些独家技巧和干货&#xff0c;帮助您提高游戏战斗力&#xff0c;享受顶级游戏作战体验&#xff01; 首先&#xff0c;让我们谈一谈战斗力升级。想要在吃鸡游…...

Vue中如何进行自定义图表与可视化图形设计

Vue中如何进行自定义图表与可视化图形设计 在现代Web应用程序开发中&#xff0c;数据可视化图表和图形设计是至关重要的一部分。Vue.js是一个流行的JavaScript框架&#xff0c;它提供了强大的工具来构建交互性强大的用户界面。本文将探讨如何在Vue.js中进行自定义图表和可视化…...

学信息系统项目管理师第4版系列19_质量管理

1. 公差 1.1. 质量测量中公差是测量指标的可允许变动范围&#xff0c;而不是实际测量值与预期值的差 1.1.1. 【高22下选35】 1.2. 结果的的可接受范围 2. 控制界限 2.1. 统计意义上稳定的过程或过程绩效的普通偏差的边界 3. 3版 3.1. 质量控制新七工具 3.1.1. 【高19下…...

react库的基础学习

React介绍 React.js是前端三大新框架&#xff1a;Angular.js、React.js、Vue.js之一&#xff0c;这三大新框架的很多理念是相同的&#xff0c;但是也有各自的特点。 React起源于Facebook的内部项目&#xff0c;因为该公司对市场上所有 JavaScript MVC 框架&#xff0c;都不满…...

FFmpeg 基础模块:容器相关的 API 操作

目录 AVFormat 模块 AVFormat 前处理部分 AVFormat 读写处理部分 小结 思考 FFmpeg 目录中包含了 FFmpeg 库代码目录、构建工程目录、自测子系统目录等&#xff0c;具体内容如下&#xff1a; 现在你知道 FFmpeg 的源代码目录中都包含了哪些内容&#xff0c;在之后使用 FFm…...

SpringMVC+统一表现层返回值+异常处理器

一、统一表现层返回值 根据我们不同的处理方法&#xff0c;返回的数据格式都会不同&#xff0c;例如添加只返回true|false&#xff0c;删除同理&#xff0c;而查询却返回数据。 Result类 为此我们封装一个result类来用于表现层的返回。 public class Result {//描述统一格式…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

测试markdown--肇兴

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

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表

##鸿蒙核心技术##运动开发##Sensor Service Kit&#xff08;传感器服务&#xff09;# 前言 在运动类应用中&#xff0c;运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据&#xff0c;如配速、距离、卡路里消耗等&#xff0c;用户可以更清晰…...

Windows安装Miniconda

一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...

k8s从入门到放弃之HPA控制器

k8s从入门到放弃之HPA控制器 Kubernetes中的Horizontal Pod Autoscaler (HPA)控制器是一种用于自动扩展部署、副本集或复制控制器中Pod数量的机制。它可以根据观察到的CPU利用率&#xff08;或其他自定义指标&#xff09;来调整这些对象的规模&#xff0c;从而帮助应用程序在负…...