首页 > 其他分享 >数据结构 ——— 链式二叉树oj题:相同的树

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

时间:2024-11-06 22:48:21浏览次数:3  
标签:assert BuyNode oj BTNode 二叉树 n1 数据结构 n4 left

目录

题目要求

手搓两个链式二叉树

代码实现 


题目要求

给你两棵二叉树的根节点 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 语句都是相辅相成的,且先后顺序不能改变
最后再利用前序遍历的思想,走完两颗树对应的位置判断是否相等

代码验证:

标签:assert,BuyNode,oj,BTNode,二叉树,n1,数据结构,n4,left
From: https://blog.csdn.net/weixin_55341642/article/details/143560428

相关文章

  • 数据结构 ——— 计算链式二叉树第k层的节点个数
    目录链式二叉树示意图手搓一个链式二叉树计算链式二叉树第k层的节点个数 链式二叉树示意图手搓一个链式二叉树代码演示://数据类型typedefintBTDataType;//二叉树节点的结构typedefstructBinaryTreeNode{BTDataTypedata;//每个节点的数据s......
  • LOJ6119 「2017 山东二轮集训 Day7」国王
    题意给定一颗树,每个点有权值\(1\)和\(-1\),称一条路径是好的当且仅当路径上所有点的权值和为\(0\)。求连续编号区间\([l,r]\)使得两个点都在\([l,r]\)的好路径比两个点都不在\([l,r]\)的好路径数严格多的方案数。\(n\le10^5\)。Sol两个端点都在区间内不好做,......
  • 数据结构学习笔记(C)--半期复习
    第一章---第四章(哈夫曼树)之前1.0绪论1.1数据结构三要素:逻辑结构a.线性​ 线性结构--一对一b.非线性​ 集合结构--属于同一集合”​ 树结构--一对多​ 图结构或网状结构--多对多存储结构顺序链式数据的运算1.2数据类型和抽象数据类型抽象数据类型ADT抽......
  • C语言数据结构--详细讲解算法复杂度
    C语言数据结构-算法复杂度前言一、时间复杂度1.大O渐进表示法2时间复杂度的计算二、空间复杂度1.什么是空间复杂度2时间复杂度的计算总结前言我们都清楚计算机存储和组织数据是通过数据结构来实现的。当计算机对这些数据结构中的数据进行遍历等操作时,这个过程就......
  • 代码随想录算法训练营第十八天|leetcode530.二叉搜索树的最小绝对差、leetcode501.二
    1leetcode530.二叉搜索树的最小绝对差题目链接:530.二叉搜索树的最小绝对差-力扣(LeetCode)文章链接:代码随想录视频链接:你对二叉搜索树了解的还不够!|LeetCode:98.验证二叉搜索树_哔哩哔哩_bilibili思路:定义一个极大值作为结果,然后在中序遍历过程中进行比较出结果1.1自己的......
  • qoj8542 Add One 2
    大概是把官方题解再说一遍。注意到,给\(k\)个数加一的代价为\(k\)。定义一个序列\(S\)合法当且仅当:对于初始为全\(0\)的序列\(B\),可以通过对\(B\)进行多次给定的两种操作得到\(S\)。可以把题意转化为:给定序列\(A\),对于所有合法序列\(S\),且\(\foralliS_i\geqA_......
  • Python——数据结构与算法-时间复杂度&空间复杂度-链表&树状结构
    1.数据结构和算法简介程序可以理解为:程序=数据结构+算法概述/目的:都可以提高程序的效率(性能)数据结构指的是存储,组织数据的方式.算法指的是为了解决实际业务问题而思考思路和方法,就叫:算法.2.算法的5大特性介绍概述:为了解决实际业务问题,......
  • C++手撕 --基本数据结构的简单实现(2)
    C++面试手撕代码----基本数据结构的简单实现(2)1.哈希表(unordered_map):#include<vector>#include<iostream>#include<list>//forlist#include<utility>//forpair#include<functional>//forstd::hashusingnamespacestd;template<typ......
  • 数据结构树与二叉树
    语雀链接:https://www.yuque.com/g/wushi-ls7km/ga9rkw/qw8kwzxigbx61kxy/collaborator/join?token=2vdSjDBgJyJb0VSL&source=doc_collaborator#《树与二叉树》......
  • LOJ6118 「2017 山东二轮集训 Day7」鬼牌
    题意有\(n\)个球,\(m\)种颜色,\(i\)种颜色有\(a_i\)个球。每次随机选择两个球\(x\),\(y\)。使两个球的颜色都变为\(y\)的颜色。问最终只有一个颜色的球的期望步数。\(n\le10^9,m\le10^5\)。Sol显然的,考虑先枚举最终颜色,我们只关心当前有多少个最终颜色的球。......