检查两颗树是否相同＜难度系数⭐＞

📝 题述：给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

💨 示例 1：

输入：p = [1,2,3], q = [1,2,3]
输出：true

💨 示例 2：

输入：p = [1,2], q = [1,null,2]
输出：false

💨 示例 3：

输入：p = [1,2,1], q = [1,1,2]
输出：false

⚠ 注意：

1️⃣ 两棵树上的节点数目都在范围 [0, 100] 内

2️⃣ -10^4^ <= Node.val <= 10^4^

🧷 平台：Visual studio 2017 && windows

🔑 核心思想：在递归时每一层函数的栈帧中存在这样的条件：p 为空，q 也为空，返回 true；p 或者 q 只有一个为空，返回 false；p 和 q 的 val 不等，返回 false；否则 p 和 q 的 val 是相等的才递归

leetcode原题

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

typedef int BTDataType;
typedef struct TreeNode 
{
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
}BTNode;

//malloc空间
BTNode* BuyNode(BTDataType x)
{
	BTNode* node = malloc(sizeof(BTNode));
	node->val = x;
	node->left = NULL;
	node->right = NULL;

	return node;
}
//创建树1
BTNode* CreatBinaryTree1()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);

	node1->right = node2;
	node2->left = node3;

	return node1;
}
//创建树2
BTNode* CreatBinaryTree2()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);

	node1->right = node2;
	node2->left = node3;

	return node1;
}
//相同的树
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
	//p为空，q也为空
	if (p == NULL && q == NULL)
		return true;
	//p和q只有1个为空
	if (p == NULL || q == NULL)
		return false;
	//p和q的val不等
	if (p->val != q->val)
		return false;
	//相等递归
	return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
int main()
{
	BTNode* root1 = CreatBinaryTree1();
	BTNode* root2 = CreatBinaryTree2();
	printf("%d\n", isSameTree(root1, root2));
	return 0;
}