二叉树OJ题:LeetCode--100.相同的树

news/2024/11/23 20:48:11/

朋友们、伙计们,我们又见面了,本期来给大家解读一下LeetCode中第100道二叉树OJ题,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成!

数据结构与算法专栏:数据结构与算法

个  人  主  页 :stackY、

C 语 言 专 栏C语言:从入门到精通

LeetCode--100.相同的树:https://leetcode.cn/problems/same-tree/

目录

1.题目介绍

2.实例演示

3.解题思路

代码实现:

递归展开图:


1.题目介绍

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

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

2.实例演示

简单的来说就是来判断两棵二叉树的对应结点是否完全相同。

3.解题思路

判断两棵二叉树是否相等最先想到的方法就是遍历,使用结点依次比较,那么二叉树的遍历方法有许多:

1. 前序遍历:根节点、左子树、右子树

2. 中序遍历:左子树、根节点、右子树

3. 后序遍历:左子树、右子树、根节点

4. 层序遍历:一层一层遍历二叉树

以上内容可以参考:https://blog.csdn.net/Yikefore/article/details/130859450?spm=1001.2014.3001.5501

那么该选用哪种遍历二叉树的方法呢? 前序遍历是比较合适的,因为前序遍历首先访问的就是根节点,如果两棵树的根节点都不相等那么就没有必要再继续往下面进行比较了,那么关于这道题最终还是要归为这棵树的子问题,也就是它的左右子树,所以使用递归实现。

在做题时要注意几个问题:

1. 结束标志--两棵树为空树、结点不相等

2. 若两棵树都为空,需要返回true,两棵树都为空满足相同的结点

3. 有一棵树为空,另一棵树不为空,就需要结束

代码实现:

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/bool isSameTree(struct TreeNode* p, struct TreeNode* q){//判断两棵树是否都为空树if(p == NULL && q == NULL)return true;//其中一颗为空就结束if(p == NULL || q == NULL)return false;//若都不为空,则比较结点是否相等if(p->val != q->val)return false;//树不为空,并且根节点相等,继续递归子问题,判断左右子树return isSameTree(p->left,q->left)&& isSameTree(p->right,q->right);
}

代码解读:

首先我们对两棵树进行检查,判断两棵树是否都为空树,如果两棵树都为空树,即两棵树相等,即可返回true,如果两棵树都不为空,进行下一步的判断其中只有一棵树为空,若其中只有一颗树为空,那么表示两棵树不相等,即可返回false,若两棵树都不为空,即可判断它们的结点是否相等,若不相等,直接返回false,若相等,则直接递归判断它们的左右子树,又重新转化为了子问题,直到将两颗树全部遍历完毕。

递归展开图:

 

朋友们、伙计们,美好的时光总是短暂的,我们本期的的分享就到此结束,最后看完别忘了留下你们弥足珍贵的三连喔,感谢大家的支持!  


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

相关文章

excel批量插入图片url显示方法

步骤&#xff1a; 1.建个t.html页面&#xff0c;并写好格式数据 <html> <head></head> <body> <table border"1" align"center"> <!--这里excel数据粘贴处--></table> </html> 2.整理好excel的表格格式…

python爬取网页文字和图片_简单的爬虫:爬取网站内容正文与图片

我们来写个简单的爬虫#### 需要用到的模块 需要用到python的urllib和lxml模块&#xff0c;urllib为python的自带模块&#xff0c;lxml需要自行安装&#xff1a;pip install lxml 简单介绍urllib和lxml的使用 我们使用urllib来爬去一个网页比如&#xff1a;In [1]: import urlli…

Scala 面向对象【中】

Scala 面向对象&#xff08;中&#xff09; 1、继承和多态 用法和Java基本一致。 基本语法 class 子类名 extends 父类名称 {} 案例演示 object Test07_Inherit {def main(args: Array[String]): Unit {val student new Student1("GG Bond",18)student.printIn…

Qt官方示例:Fridge Magnets Example(冰箱贴)

冰箱贴类&#xff1a; #include "draglabel.h" #include <QtWidgets>DragLabel::DragLabel(const QString &text, QWidget *parent): QLabel(parent) {QFontMetrics metric(font());QSize size metric.size(Qt::TextSingleLine, text);QImage image(size…

2.3 案例3 加点料-增加一张图片

本案例对应的源代码目录&#xff1a;src/chapter02/ks02_03。程序运行效果见图2-21。 图2-21 案例3运行效果 既然要进行界面编程&#xff0c;自然离不开图片。如果认为在按钮上使用文字太枯燥了&#xff0c;那么使用图标是不是会更好呢&#xff1f;本节讨论一下如何在Qt项目中…

微信缓存dat怎么转图片_PC微信dat如何转图片?方式方法

微信dat转码软件使用操作说明在线解码,各位同学下载软件后&#xff0c;如何操作?如何找到dat文件?如何使用?又有哪些注意事项呢?这里会为大家一一道来。问题1 &#xff1a;如果下载失败怎么办?请先检查网络&#xff0c;软件并没有放在我的网站上&#xff0c;而是放在大厂七…

html5无法处理像素点导致图片花了,教你使用Canvas处理图片的方法

Canvas&#xff0c;中文译为“画布”&#xff0c;HTML5中新增了元素&#xff0c;可以结合JavaScript动态地在画布中绘制图形。 今天&#xff0c;我们不讲Canvas的图形绘制&#xff0c;而是讲如何对图片进行处理。 大概流程非常简单&#xff0c;主要分为以下三个步骤&#xff1a…

计算机教室英语手抄报图片,英语手抄报图片四年级

英语手抄报图片四年级 四年级的小朋友们&#xff0c;下面是有关四年级上册英语单词表图片手抄报内容知识&#xff0c;欢迎大家阅读与了解。 小学四年级上册英语单词表&#xff1a;Unit 1 My Classroom window 窗户  board 写字板  light 灯;管灯  picture 画;图画 door 门…