(二叉树) 100. 相同的树 ——【Leetcode每日一题】

news/2024/4/19 2:24:35

❓100. 相同的树

难度:简单

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

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

示例 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 ] [0, 100] [0,100]
  • − 1 0 4 < = N o d e . v a l < = 1 0 4 -10^4 <= Node.val <= 10^4 104<=Node.val<=104

💡思路:深度优先搜索

  1. 如果根节点都为空,返回 true
  2. 如果其中一个为空,或者两个根节点的 val 值不同,则返回 false
  3. 然后递归判断左右子树,如果左右子树都相同时,才返回 true

🍁代码:(Java、C++)

Java

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {if(p == null && q == null) return true;if((p == null || q == null) || p.val != q.val) return false;return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);}
}

C++

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool isSameTree(TreeNode* p, TreeNode* q) {if(p == nullptr && q == nullptr) return true;if((p == nullptr || q == nullptr) || p->val != q->val) return false;return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);}
};

🚀 运行结果:

在这里插入图片描述

🕔 复杂度分析:

  • 时间复杂度 O ( m i n ( m , n ) ) O(min(m,n)) O(min(m,n)),其中 mn 分别是两个二叉树的节点数。对两个二叉树同时进行深度优先搜索,只有当两个二叉树中的对应节点都不为空时才会访问到该节点,因此被访问到的节点数不会超过较小的二叉树的节点数。
  • 空间复杂度 O ( m i n ( m , n ) ) O(min(m,n)) O(min(m,n)),空间复杂度取决于递归调用的层数,递归调用的层数不会超过较小的二叉树的最大高度,最坏情况下,二叉树的高度等于节点数。

题目来源:力扣。

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

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


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

相关文章

用docker搭建selenium grid分布式环境实践

目录 前言&#xff1a; selenium jar包直接启动节点 用docker命令直接启动 docker-compose 启动 Hub和node在一台机器上 Hub和node不在一台机器上 遗留问题 总结 前言&#xff1a; Selenium是一个流行的自动化测试工具&#xff0c;支持多种编程语言和多种浏览器。Sele…

编译原理笔记12:自上而下语法分析(2)非递归预测分析器、FIRST FOLLOW 集合计算

目录 使用预测分析器的自上而下分析格局 使用预测分析器进行分析的实例FIRST、FOLLOW 集合的构造FIRST 集合FOLLOW 集合 使用预测分析器的自上而下分析 使用预测分析器进行的自上而下分析是非递归的。预测分析器模型其实是一种 PDA&#xff08;下推自动机&#xff0c;Pushdown…

一文了解快手广告生态:磁力智投、磁力金牛、磁力聚星、磁力万象、磁力方舟!

&#xff08;抖音和快手的对照表&#xff09; 通过抖音和快手的对照表&#xff0c;我们可以知道磁力智投是快手的信息流投放平台&#xff0c;主要做站外引流&#xff0c;磁力金牛则对标巨量千川&#xff0c;主要做快手电商的站内闭环&#xff0c;磁力聚星则是围绕着达人营销&a…

Golang 中goroutine、channel 生产环境中例子和应用

学习目标: Golang 学习生产环境中例子和应用 学习内容: 大家好,今天我们来聊一聊goroutine、channel产品开发中的应用。如果你还不知道这些是什么,那么恭喜你,你来对地方了!因为我也不知道。 好了,开玩笑了。其实这些都是Go语言中非常重要的概念,尤其是在并发编程中。…

linux centos 编译安装jdk8

下载JDK安装包 首先&#xff0c;你需要从Oracle的官方网站下载需要的JDK版本&#xff0c;这里以JDK8为例。 下载链接&#xff1a;https://www.oracle.com/technetwork/java/javase/downloads/jdk8-downloads-2133151.html安装依赖 在编译安装前&#xff0c;需要安装一些必备的依…

樱花雨特效完整源码

特效中所需的图片、音乐及JQ源码文件麻烦自行下载有任何其他问题可留言 CSS 完整代码 @charset "utf-8"; *{margin:0;padding:0; } body{max-width: 100%;min-width: 100

春天樱花飘落flash源文件

春天樱花飘落flash源文件是一款绿色清新的flash樱花掉落动画素材下载 春天樱花飘落flash源文件下载地址&#xff1a;http://www.huiyi8.com/sc/4060.html(转载请注明此处&#xff09;

html5 canvas带音效的新年烟花特效,真的好看极了

花了半个小时写的代码&#xff0c;这个html5 canvas新年烟花一定不会让大家失望&#xff01; 首先我们看下静态的效果图&#xff1a; 文章末尾有动态的效果图&#xff0c;滑动即可看到&#xff01; 如果大家源码下载效果出不来可以加我的前端学习群&#xff1a;733581373&…

拯救动画卡顿之FLIP

前置知识 什么是FPS FPS是浏览器的每秒的渲染帧数&#xff0c;也就是浏览器切换画面的次数&#xff0c;大多数设备的刷新率都是60FPS&#xff0c;一般来说FPS越低页面就会越卡顿。 什么是像素管道&#xff1f; 像素管道是浏览器单个帧的渲染流水线&#xff0c;如果其中有某…

樱花飞舞

<!doctype html> <html> <head> <meta charset="utf-8"> <title>樱花漫天飞舞</title> </head> <style> body {padding:0; margin:0; overflow:hidden; height: 600px; position: relative;} canvas {padding:0; ma…

樱花飘落,3D效果,抖音热门樱花飘落html

樱花飘落&#xff0c;3D效果&#xff0c;抖音热门樱花飘落html 总结 代码如下&#xff08;示例&#xff09;&#xff1a; <!DOCTYPE html><html><head><title>樱花飘落</title><style type"text/css" media"screen">…

樱花特效

下面是代码&#xff0c;如果感觉有帮助的话留个赞吧。 <!doctype html> <html> <head> <meta charset"utf-8"> <title>樱花雨</title> <script >/*! jQuery v1.10.2 | (c) 2005, 2013 jQuery Foundation, Inc. | jquery…

springboot启动流程 (3) 自动装配

在SpringBoot中&#xff0c;EnableAutoConfiguration注解用于开启自动装配功能。 本文将详细分析该注解的工作流程。 EnableAutoConfiguration注解 启用SpringBoot自动装配功能&#xff0c;尝试猜测和配置可能需要的组件Bean。 自动装配类通常是根据类路径和定义的Bean来应…

【Centos系统故障】虚拟机断电后centos7无法正常启动 XFS(sda3)

1. 背景&#xff1a; 虚拟机断电后centos7无法正常启动 XFS(sda3)&#xff0c;通常都是断电以及非法关机&#xff0c;杀掉虚拟机等突然中断系统的情况&#xff0c;会导致内存数据损坏&#xff0c;从而导致linux操作系统无法启动。 2. 解决办法&#xff1a; 清理掉内存数据&a…

盖雅工场荣膺第二届山东人力资源服务创新大赛信息科技创新赛道一等奖

6月20日&#xff0c;第二届山东人力资源服务创新大赛决赛落下帷幕。经过激烈角逐&#xff0c;盖雅工场脱颖而出&#xff0c;荣膺信息科技创新赛道一等奖。 关于第二届山东人力资源服务创新大赛 第二届山东人力资源服务创新大赛是由山东省人力资源和社会保障厅、威海市人民政府…

【无标题】Instant NGP(使用哈希编码的多分辨率的即时神经图形原语)

论文基本信息 作者&#xff1a;THOMAS MLLER&#xff0c;NVIDIA&#xff0c;瑞士ALEX EV ANS&#xff0c;NVIDIA&#xff0c;英国CHRISTOPH SCHIED&#xff0c;美国NVIDIA ALEXANDER KELLER&#xff0c;德国 关键词&#xff1a; Image Synthesis, Neural Networks, En- codings…

计算机基础打印机,计算机基础知识:打印机的安装

Windows系统中的打印机安装可以分为本地打印机和网络打印机的安装。本地打印机就是连接在自己计算机上的打印机&#xff0c;网络打印机就是指通过局域网共享其他计算机上安装的打印机。下面我们就来为大家详细的讲解打印机的这两种安装方法。 一、安装本地打印机 首先将打印机和…

小米米家打印机,打印状态提示出错无法正常打印,怎么办?

环境&#xff1a; 电脑&#xff1a;组装机 系统&#xff1a;Win7 旗舰版 打印机&#xff1a;小米米家喷墨打印机 问题描述&#xff1a; 小米米家打印机&#xff0c;打印状态提示出错无法正常打印&#xff0c;怎么办&#xff1f;之前脱机了&#xff0c;连机就出现这个提示。…

树莓派设备喷墨打印机定时打印

买了款喷墨打印机&#xff0c;为了防堵喷头&#xff0c;直接上代码吧 树莓派型号&#xff1a;树莓派 zero w 板子 打印机型号&#xff1a;HP Smart Tank 510 series python版本&#xff1a;Python 3.9.2 原因&#xff1a;树莓派和打印机都并非一直开机。本人也并非一直在家…

打印机相关的c语言程序,VC下打印机的使用

VC 5.0是开发Windows 95下应用程序的强大工具。本文将通过一 个具体实例讨论用VC打印文字和图形的一些技术。在Windows 95下, 显示器和打印机、绘图仪都被视为输出设备。系统默认的输出设备是 显示器。要使用打印机,首先需要创建一个指向打印机的设备环境句柄, 然后通过该句柄调…