数据结构 ——— 链式二叉树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 语句都是相辅相成的，且先后顺序不能改变
最后再利用前序遍历的思想，走完两颗树对应的位置判断是否相等

代码验证：