力扣第100题 相同的数 c++ 二叉 简单易懂+注释

题目

100. 相同的树

简单

给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。

示例 1:

输入:p = [1,2,3], q = [1,2,3]
输出:true

示例 2:

输入:p = [1,2], q = [1,null,2]
输出:false

示例 3:

输入:p = [1,2,1], q = [1,1,2]
输出:false

提示:

  • 两棵树上的节点数目都在范围 [0, 100] 内
  • -104 <= Node.val <= 104

思路和解题方法

  1. bool isSameTree(TreeNode* p, TreeNode* q):这是一个名为isSameTree的函数,它接受两个参数pq,分别表示要比较的两个二叉树的根节点。返回值类型为bool,表示两个二叉树是否相同。

  2. if (p == nullptr && q == nullptr):首先判断两个节点pq是否都为空。如果是,则表示这两个子树是相同的,没有节点需要比较,直接返回true

  3. else if (p == nullptr || q == nullptr):如果只有一个节点为空,而另一个节点不为空,这说明这两个子树不相同,因为它们的节点数量不同。在此情况下,直接返回false

  4. else if (p->val != q->val):如果两个节点都不为空,但它们的值不相同,说明这两个子树不相同,直接返回false

  5. else:当两个节点都不为空且它们的值相等时,我们需要进一步比较它们的左右子树。递归调用isSameTree函数,传入左子树的左孩子和右子树的右孩子,以及左子树的右孩子和右子树的左孩子。只有当这两个递归调用都返回true时,才说明整个树是相同的,返回true

复杂度

        时间复杂度:

                O(n。c)

时间复杂度是O(n),其中n表示两个二叉树中节点数的最大值。这个复杂度是因为在最坏情况下,需要访问两个二叉树的所有节点,因此时间复杂度是线性的。

        空间复杂度

                O(n)

空间复杂度也是O(n),由于递归调用,每个函数调用都会将一些数据压入堆栈中,因此需要O(n)的空间来存储这些信息(其中n表示树的高度)。在最坏情况下,两个树的高度相同,因此空间复杂度与节点数成正比。

c++ 代码

class Solution {
public:// 判断两个二叉树是否相同的函数bool isSameTree(TreeNode* p, TreeNode* q) {// 如果两个节点都是空,则表示这两个子树是相同的,直接返回trueif (p == nullptr && q == nullptr) {return true;} // 如果只有一个节点为空,则表示这两个子树不相同,直接返回falseelse if (p == nullptr || q == nullptr) {return false;} // 如果两个节点的值不相同,则表示这两个子树不相同,直接返回falseelse if (p->val != q->val) {return false;} // 递归比较左右子树的节点,只有左右子树的对应节点都相同时,// 才表示这两个子树相同,因此需要对两个子树递归调用此函数else {return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);}}
};

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

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

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/149957.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

RabbitMQ之Direct(直连)Exchange解读

目录 基本介绍 使用场景 springboot代码演示 演示架构 工程概述 RabbitConfig配置类&#xff1a;创建队列及交换机并进行绑定 MessageService业务类&#xff1a;发送消息及接收消息 主启动类RabbitMq01Application&#xff1a;实现ApplicationRunner接口 基本介绍 在r…

功能测试复习

一。测试流程 1.需求评审 确保各部门需求理解一致 2.计划编写 测什么&#xff0c;谁来测&#xff0c;怎么测 3.用例设计 验证项目是否符合需求的操作文档 4.用例执行 项目模块开发完成开始执行用例文档实施测试 5.缺陷管理 对缺陷进行…

[晕事]今天做了件晕事21;设置代理访问网站的时候需注意的问题

今天在家上班&#xff0c;设置好VPN&#xff0c;通过代理来访问公司内部的一个系统浏览器的反应如下&#xff1a; Hmmm… can’t reach this page ***.com refused to connect. 这个返回的错误&#xff0c;非常的具有迷惑性&#xff0c;提示的意思&#xff1a;拒绝链接&#xf…

李沐深度学习记录2:10多层感知机

一.简要知识记录 x.numel()&#xff1a;看向量或矩阵里元素个数 A.sum()&#xff1a;向量或矩阵求和&#xff0c;axis参数可对某维度求和&#xff0c;keepdims参数设置是否保持维度不变 A.cumsum&#xff1a;axis参数设置沿某一维度计算矩阵累计和x*y:向量的按元素乘法 torch.…

时间序列常用数据处理

1.组合技巧Compose 1.2 实例应用及其解释 # 用于组合多个数据处理方法 class Compose(object):def __init__(self, transforms):self.transforms transformsdef __call__(self, seq):for t in self.transforms:seq t(seq)return seq 这段Python代码定义了一个名为Compose的…

【Spring Boot】日志文件

日志文件 一. 日志文件有什么用二. 日志怎么用三. ⾃定义⽇志打印1. 在程序中得到⽇志对象2. 使⽤⽇志对象打印⽇志3. ⽇志格式说明 四. 日志级别1. ⽇志级别有什么⽤2. ⽇志级别的分类与使⽤ 五. 日志持久化六. 更简单的⽇志输出—lombok1. 添加 lombok 依赖2. 输出⽇志3. lom…

Javascript - 轮播图

轮播图也称banner图、广告图、焦点图、滑片。是指在一个模块或者窗口,通过鼠标点击或手指滑动后,可以看到多张图片。这些图片统称为轮播图,这个模块叫做轮播模块。可以通过运用 javascript去实现定时自动转换图片。以下通过一个小Demo演示如何运用Javascript实现。 <!DOCTYP…

《计算机视觉中的多视图几何》笔记(12)

12 Structure Computation 本章讲述如何在已知基本矩阵 F F F和两幅图像中若干对对应点 x ↔ x ′ x \leftrightarrow x x↔x′的情况下计算三维空间点 X X X的位置。 文章目录 12 Structure Computation12.1 Problem statement12.2 Linear triangulation methods12.3 Geomet…

【Java】内部类

目录 概念&#xff1a; 内部类访问特点 示例代码&#xff1a; 运行结果&#xff1a; 内部类分类 1. 成员内部类 示例代码&#xff1a; 2. 静态内部类 示例代码&#xff1a; 3. 方法内部类(局部内部类) 示例代码&#xff1a; 4. 匿名内部类 示例代码&#xff1a; 概…

【开发篇】十七、消息:模拟订单短信通知

文章目录 1、消息2、JMS3、AMQP4、案例&#xff1a;模拟订单短信通知 相关文章&#xff1a; 【同步通讯与异步通讯】 1、消息 消息的发送方&#xff0c;即生产者。消息的接收方&#xff0c;即消费者。同步通信就行打视频&#xff0c;等着对方接电话才能继续往下&#xff0c;而…

文件编码格式

一、问题场景 笔者在写controller层出现了一些小问题&#xff1a;测试controller层的一些请求的时候&#xff0c;后端控制台打印的是乱码&#xff0c;网上找了很多说改UTF-8的&#xff0c;但是我去设置里面全部都改为UTF-8了&#xff0c;结果仍然无济于事&#xff0c;甚至还把…

泊车功能专题介绍 ———— AVP系统基础数据交互内容

文章目录 系统架构系统功能描述云端子系统车辆子系统场端子系统用户APP 工作流程基础数据交互内容AVP 系统基础数据交互服务车/用户 - 云基础数据交互内容车位查询工作流程技术要求数据交互要求 车位预约工作流程技术要求数据交互要求 取消预约工作流程技术要求数据交互要求 泊…

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

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

关于MAC电脑无法正常登陆H3C iNodes登陆的解决办法

背景 前段时间&#xff0c;单位的网络在做升级改造&#xff0c;网络出口也进行彻底调整同时单位的网络出口设备做了机房物理迁移&#xff0c;迁移后网络正常使用&#xff0c;但是出现自己的MAC电脑无法登陆iNodes问题&#xff0c;总是出现“正在查询SSL 网关参数..查询SSL 网关…

sheng的学习笔记-【中文】【吴恩达课后测验】Course 2 - 改善深层神经网络 - 第二周测验

课程2_第2周_测验题 目录&#xff1a;目录 第一题 1.当输入从第8个mini-batch的第7个的例子的时候&#xff0c;你会用哪种符号表示第3层的激活&#xff1f; A. 【  】 a [ 3 ] { 8 } ( 7 ) a^{[3]\{8\}(7)} a[3]{8}(7) B. 【  】 a [ 8 ] { 7 } ( 3 ) a^{[8]\{7\}(3)} a…

无状态自动配置 DHCPv6无状态配置 DHCPv6有状态配置

1、无状态自动配置 配置命令 AR1 ipv6 #开启路由器ipv6报文转发功能 interface GigabitEthernet0/0/0 ipv6 enable #开启路由器接口IPv6报文转发功能 ipv6 address FC01::1/64 …

怎么将Linux上的文件上传到github上

文章目录 1. 先在window浏览器中创建一个存储项目的仓库2. 复制你的ssh下的地址1) 生成ssh密钥 : 在Linux虚拟机的终端中,运行以下命令生成ssh密钥2)将ssh密钥添加到github账号 : 运行以下命令来获取公钥内容: 3. 克隆GitHub存储库&#xff1a;在Linux虚拟机的终端中&#xff0…

Springboot实现登录功能(token、redis、登录拦截器、全局异常处理)

登录流程&#xff1a; 1、前端调用登录接口&#xff0c;往接口里传入账号&#xff0c;密码 2、根据账号判断是否有这个用户&#xff0c;如果有则继续判断密码是否正确 3、验证成功后&#xff0c;则是根据账号&#xff0c;登录时间生成token&#xff08;用JWT&#xff09; 4、将…

数据结构与算法(四):哈希表

参考引用 Hello 算法 Github&#xff1a;hello-algo 1. 哈希表 1.1 哈希表概述 哈希表&#xff08;hash table&#xff09;&#xff0c;又称散列表&#xff0c;其通过建立键 key 与值 value 之间的映射&#xff0c;实现高效的元素查询 具体而言&#xff0c;向哈希表输入一个键…

VR开发(一)——SteamVR实现摇杆移动

一、基础环境搭建 1.AssetStore 找到SteamVR并导入&#xff1b; 2.添加一个 VR 中代表玩家自己的物体。我可以打开 Assets/SteamVR/InteractionSystem/Core 文件夹&#xff0c;将 Player 物体拖入场景&#xff1a; 二、修改手柄按钮映射集 3.windows/steamVR input&#xff…