数据结构 ——— 链式二叉树oj题:相同的树

目录

题目要求

手搓两个链式二叉树

代码实现 


题目要求

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

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


手搓两个链式二叉树

代码演示:

// 数据类型
typedef int BTDataType;

// 二叉树节点的结构
typedef struct BinaryTreeNode
{
	BTDataType data; //每个节点的数据

	struct BinaryTreeNode* left; //指向左子树的指针

	struct BinaryTreeNode* right; //指向右子树的指针
}BTNode;

// 申请新节点
BTNode* BuyNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));

	// 判断是否申请成功
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}

	// 初始化
	newnode->data = x;
	newnode->left = NULL;
	newnode->right = NULL;

	return newnode;
}

// 树1
BTNode* CreatBinaryTree1()
{
	BTNode* n1 = BuyNode(1);
	assert(n1);
	BTNode* n2 = BuyNode(2);
	assert(n2);
	BTNode* n3 = BuyNode(3);
	assert(n3);
	BTNode* n4 = BuyNode(4);
	assert(n4);
	BTNode* n5 = BuyNode(5);
	assert(n5);
	BTNode* n6 = BuyNode(6);
	assert(n6);
	
	n1->left = n2;
	n1->right = n4;
	n2->left = n3;
	n4->left = n5;
	n4->right = n6;

	return n1;
}

// 树2
BTNode* CreatBinaryTree2()
{
	BTNode* n1 = BuyNode(1);
	assert(n1);
	BTNode* n2 = BuyNode(2);
	assert(n2);
	BTNode* n3 = BuyNode(3);
	assert(n3);
	BTNode* n4 = BuyNode(4);
	assert(n4);
	BTNode* n5 = BuyNode(5);
	assert(n5);
	BTNode* n6 = BuyNode(6);
	assert(n6);
	
	n1->left = n2;
	n1->right = n4;
	n2->left = n3;
	n4->left = n5;
	n4->right = n6;

	return n1;
}

代码实现

代码演示: 

bool isSameTree(BTNode* p, BTNode* q)
{
	if (p == NULL && q == NULL)
		return true;

	if (p == NULL || q == NULL)
		return false;

	if (p->data != q->data)
		return false;

	return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

代码解析:

第一个 if 语句用于判断是否同时为空
因为第一个 if 语句判断了是否为空的情况,所以第二个 if 语句只要执行了,那么必定有一个节点不为空,所以就不相等,返回 false
而第三个 if 语句就是用于判断两个树相对应的节点数据是否相同,不同就返回 false
以上三个 if 语句都是相辅相成的,且先后顺序不能改变
最后再利用前序遍历的思想,走完两颗树对应的位置判断是否相等

代码验证:

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

对标 Windows Copilot 的 UOS AI,升级后更能打了

进入 2024 年,AI 应用迎来大爆发,不仅各类应用纷纷宣称“AI 赋能”,操作系统也不例外。前有 Windows Copilot,后有 Apple Intelligent,手机行业更是积极,各种 AI 手机纷纷发布。国产信创系统自然也不甘落后…

leetcode912.排序数组的题解

题目描述: 题目要求在不使用任何内置函数的情况下解决问题,时间复杂度为 O(nlog(n))。 笔者使用了快速排序,但是直接使用最原始的快速排序,有些特殊的测试用例会超时。 1)如果数组本身基本有序,则使用原始…

迷你版VFB,极简的Freebasic开发IDE-VB7-vb6编程开发

支持Freebasic, Js, vbs, Html5开发,可以发布成控制台程序,EXE,标准DLL,OCX控件,网站 类似Vscode, Aardio,按键精灵一样的开发工具。 本来芳芳只是想做个按键精灵办公小工具,结果一下小心搞了一…

【综合案例】使用React编写B站评论案例

一、效果展示 默认效果,一开始默认按照最热进行排序 发布了一条评论 按照最新进行排序 按照最新进行排序 二、效果说明 页面上默认有3条评论,且一开始进入页面的时候是按照点赞数量进行倒序排列展示,可以点击【最热 、最新】进行排序的切换。…

SSL证书申请终极指南

SSL验证是确认网站或服务器提供的SSL 证书的真实性和有效性的过程。 SSL证书验证是确认网站或服务器提供的SSL证书的真实性和有效性的过程。SSL证书是用于在客户端(例如Web浏览器)和服务器之间建立安全连接的数字证书。它们对于确保通过互联网传输的数据…

处理PhotoShopCS5和CS6界面字体太小

处理PhotoShop CS6界面字体太小 背景:安装PhotoShop CS6后发现无法调大字体大小,特别是我的笔记本14寸的,显示的字体小到离谱。 百度好多什么降低该电脑分辨率,更改电脑的显示图标大小,或者PS里的首选项中的界面设置。…

python中t是什么意思

python中t是什么意思? python中t指的是“\r”:回车符,返回到这一行的开头,return的意思。 其他相关: \n:换行符,到下一行的同一位置,纵坐标相同,new line的意思。 \t…

python项目实战---使用图形化界面下载音乐

音乐下载 设计思路: 设计界面编写爬虫代码绑定爬虫打包exe文件 这个是最终的设计成果,所有的下载歌曲都在“下载mp3”文件夹里面 完整代码 逻辑代码 import os.path import reimport requests from PyQt5.QtWidgets import QApplication,QWidget,QM…

Linux(inode + 软硬链接 图片+大白话)

后面也会持续更新,学到新东西会在其中补充。 建议按顺序食用,欢迎批评或者交流! 缺什么东西欢迎评论!我都会及时修改的! 在这里真的很感谢这位老师的教学视频让迷茫的我找到了很好的学习视频 王晓春老师的个人空间…

从0开始深度学习(24)——填充和步幅

1 填充 在上一节中,我们的卷积步骤如下: 可以发现输入是 3 3 3\times3 33,输出是 2 2 2\times2 22,这样可能会导致原始图像的边界丢失了许多有用信息,如果应用多层卷积核,累积丢失的像素就更多了&#…

C++:模拟实现STL的vector

目录 一.vector类 1.vector类的构造及析构 2.定义迭代器 3.size()和capacity() 4.operator [ ] 5.resize()和reserve() 6.插入和删除 二.整体代码 1.vector.h 2.vector.cpp 上一节中了解了vector中部分接口的使用,在这里我们模拟实现vector,为了避免与库中的起冲突,…

砥砺十年风雨路,向新而行创新程丨怿星科技十周年庆典回顾

10月24日,是一年中的第256天,也是程序员节,同时也是怿星的生日。2014年到2024年,年华似水匆匆一瞥,多少岁月轻描淡写,怿星人欢聚一堂,共同为怿星科技的十周年庆生! 01.回忆往昔&…

Chrome与火狐哪个浏览器的移动版本更流畅

在当今的数字化时代,移动设备已经成为我们生活中不可或缺的一部分。而浏览器作为我们访问互联网的重要工具,其性能和用户体验直接影响到我们的使用感受。本文将对比Chrome和火狐(Firefox)两款主流浏览器的移动版本,探讨…

算法练习:1004. 最大连续1的个数 III

题目链接:1004. 最大连续1的个数 III。 题目要求,给定一个数组,这个数组里面只有0或1,然后计算有多少个连续的1的最大长度,同时给了一个条件就是,可以把k个0变成1,然后来计算长度。 暴力解法&a…

【大数据技术基础 | 实验七】HBase实验:部署HBase

文章目录 一、实验目的二、实验要求三、实验原理四、实验环境五、实验内容和步骤(一)验证Hadoop和ZooKeeper已启动(二)修改HBase配置文件(三)启动并验证HBase 六、实验结果七、实验心得 一、实验目的 掌握…

LLMs之LoLCATs:《LoLCATs: On Low-Rank Linearizing of Large Language Models》翻译与解读

LLMs之LoLCATs:《LoLCATs: On Low-Rank Linearizing of Large Language Models》翻译与解读 导读:这篇论文的核心是提出了一种名为 LoLCATs (Low-rank Linear Conversion via Attention Transfer) 的方法,用于高效地将大型语言模型 (LLM) 线性…

linux命令详解,文件管理类

文件管理 stat 显示文件的详细信息,包括时间戳 stat filenametouch 主要用于更新文件的访问时间和修改时间(时间戳)。如果指定的文件不存在,touch 命令会创建一个新的空文件。 touch newfile参数 -t 更新文件的修改时间为特…

MySQL的其他函数

数学函数: 1.round 四舍五入 select round(1.45);//不管正负数,先将绝对值round,然后加正负号 select round(1.567,2); //表示小数点保留2位 2.ceil 向上取整 select ceil(-1.3); 3.floor 向下取整 4.truncate 截断 select truncate(1.65,1); // 结果保留小数…

@Excel若依导出异常/解决BusinessBaseEntity里面的字段不支持导出

今天发现所有实体类继承BusinessBaseEntity里面的这些通用字段不支持导出,debug时发现是这样: 导出效果 这里我把能查到的方法都汇总了,如果你也遇到这个异常,可以去逐步排查 1.先看库里有没有数据 2.看字段名是否对齐 3.所需要…

云数据中心基础环境-详细设计方案(364页WORD)

文档介绍: 随着云计算技术的飞速发展,云数据中心已成为企业数字化转型的核心基础设施,承载着数据存储、处理、分析和应用的重任。本设计方案旨在构建一个高性能、高可用、高安全性的云数据中心基础环境,以满足企业日益增长的业务需…