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

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...

Java编程之桥接模式

定义 桥接模式&#xff08;Bridge Pattern&#xff09;属于结构型设计模式&#xff0c;它的核心意图是将抽象部分与实现部分分离&#xff0c;使它们可以独立地变化。这种模式通过组合关系来替代继承关系&#xff0c;从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...

华为OD机考-机房布局

import java.util.*;public class DemoTest5 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseSystem.out.println(solve(in.nextLine()));}}priv…...