目录
题目要求
给你两棵二叉树的根节点 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