对称二叉树＜难度系数⭐＞&& 另一颗树的子树＜难度系数⭐＞

一、对称二叉树＜难度系数⭐＞

📝 题述：给定一个二叉树，检查它是否是镜像对称的。

💨 示例 1：

[1,2,2,3,4,4,3] 是镜像对称的

💨 示例 2：

[1,2,2,null,3,null,3] 则不是镜像对称的

🧷 平台：Visual studio 2017 && windows

🔑 核心思想：在递归时每一层函数的栈帧中存在这样的条件：root1 和 root2 同时为空，返回 true；root1 和 root2 只有一个为空返回 false；root1 和 root2 的 val 不等，返回 false；否则 root1 和 root2 是相等的继续递归。

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;
}
//创建树
BTNode* CreatBinaryTree()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(2);
	BTNode* node4 = BuyNode(3);
	BTNode* node5 = BuyNode(4);
	BTNode* node6 = BuyNode(4);
	BTNode* node7 = BuyNode(3);

	node1->left = node2;
	node1->right = node3;
	node2->left = node4;
	node2->right = node5;
	node3->left = node6;
	node3->right = node7;

	return node1;
}
//实现递归的子函数
bool _isSymmetric(struct TreeNode* root1, struct TreeNode* root2) {
	//root1和root2同时为空
	if (root1 == NULL && root2 == NULL)
		return true;
	//root1和root2只有一个为空
	if (root1 == NULL || root2 == NULL)
		return false;
	//root1和root2的val不等
	if (root1->val != root2->val)
		return false;
	//相等继续递归
	return _isSymmetric(root1->left, root2->right) && _isSymmetric(root1->right, root2->left);
}
//对称二叉树
bool isSymmetric(struct TreeNode* root) {
	//空树就返回true
	if (root == NULL)
		return true;
	//否则调用子函数判断左右子树
	return _isSymmetric(root->left, root->right);
}
int main()
{
	BTNode* root = CreatBinaryTree();
	printf("%d\n", isSymmetric(root));
	return 0;
}

二、另一颗树的子树＜难度系数⭐＞

📝 题述：给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

💨 示例 1：

输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true

💨 示例 2：

输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出：false

⚠ 注意：

1️⃣ root 树上的节点数量范围是 [1, 2000]

2️⃣ subRoot 树上的节点数量范围是 [1, 1000]

3️⃣ -104 <= root.val <= 104

4️⃣ -104 <= subRoot.val <= 104

🧷 平台：Visual studio 2017 && windows

🔑 核心思想：每一层函数栈帧中都包括：如果 root 等于空，返回 false；如果调用相同的树为真，返回 true；否则继续递归

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(3);
	BTNode* node2 = BuyNode(4);
	BTNode* node3 = BuyNode(5);
	BTNode* node4 = BuyNode(1);
	BTNode* node5 = BuyNode(2);

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

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

	node1->left = node2;
	node1->right = 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);
}
//另一棵树的子树
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
	//root等于空
	if (root == NULL)
		return false;
	//调用相同的树
	if (isSameTree(root, subRoot))
		return true;
	//继续递归
	return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}
int main()
{
	BTNode* root1 = CreatBinaryTree1();
	BTNode* root2 = CreatBinaryTree2();

	printf("%d\n", isSubtree(root1, root2));

	return 0;
}