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

代码验证：