当前位置: 首页 > 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 {//描述统一格式…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

Xshell远程连接Kali(默认 | 私钥)Note版

前言:xshell远程连接&#xff0c;私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

在建筑行业&#xff0c;项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升&#xff0c;传统的管理模式已经难以满足现代工程的需求。过去&#xff0c;许多企业依赖手工记录、口头沟通和分散的信息管理&#xff0c;导致效率低下、成本失控、风险频发。例如&#…...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:

根据万维钢精英日课6的内容&#xff0c;使用AI&#xff08;2025&#xff09;可以参考以下方法&#xff1a; 四个洞见 模型已经比人聪明&#xff1a;以ChatGPT o3为代表的AI非常强大&#xff0c;能运用高级理论解释道理、引用最新学术论文&#xff0c;生成对顶尖科学家都有用的…...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)

目录 一、&#x1f44b;&#x1f3fb;前言 二、&#x1f608;sinx波动的基本原理 三、&#x1f608;波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、&#x1f30a;波动优化…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...

Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战

说明&#xff1a;这是一个机器学习实战项目&#xff08;附带数据代码文档&#xff09;&#xff0c;如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下&#xff0c;风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...

SQL慢可能是触发了ring buffer

简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...