🚀write in front🚀
📜所属专栏：初阶数据结构
🛰️博客主页：睿睿的博客主页
🛰️代码仓库：🎉VS2022_C语言仓库
🎡您的点赞、关注、收藏、评论，是对我最大的激励和支持！！！
关注我，关注我，关注我，你们将会看到更多的优质内容！！

前言

  在二叉树的学习中，我们学习了递归的思想，但是还需要刷题来真正弄明白这种思想。希望下面的几道经典oj题对你有所帮助。

1. 单值二叉树

OJ链接

深度优先搜索

  一棵树的所有节点都有相同的值，当且仅当对于树上的每一条边的两个端点，它们都有相同的值（这样根据传递性，所有节点都有相同的值）。

  因此，我们可以对树进行一次深度优先搜索。当搜索到节点 x 时，我们检查 x与 x 的每一个子节点之间的边是否满足要求。例如对于左子节点而言，如果其存在并且值与 x 相同，那么我们继续向下搜索该左子节点；如果值与 x不同，那么我们直接返回 False。

bool isUnivalTree(struct TreeNode* root)
{if(root==NULL){return true;}if(root->left!=NULL&&root->val!=root->left->val){return false;}if(root->right!=NULL&&root->val!=root->right->val){return false;}return  isUnivalTree(root->left)&&isUnivalTree(root->right);
}

2. 检查两颗树是否相同

OJ链接

  如果两个二叉树都为空，则两个二叉树相同。如果两个二叉树中有且只有一个为空，则两个二叉树一定不相同。

  如果两个二叉树都不为空，那么首先判断它们的根节点的值是否相同，若不相同则两个二叉树一定不同，若相同，再分别判断两个二叉树的左子树是否相同以及右子树是否相同。这是一个递归的过程，因此可以使用深度优先搜索，递归地判断两个二叉树是否相同。

bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{if(p==NULL&&q==NULL){return true;}if(p==NULL||q==NULL){return false;}if(p->val!=q->val){return false;}return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}

3. 对称二叉树

OJ链接

如果一个树的左子树与右子树镜像对称，那么这个树是对称的。

因此，该问题可以转化为：两个树在什么情况下互为镜像？

如果同时满足下面的条件，两个树互为镜像：

• 它们的两个根结点具有相同的值
• 每个树的右子树都与另一个树的左子树镜像对称

我们可以实现这样一个递归函数，左子树的右子树与右子树的左子树相同，左子树的左子树与右子树的右子树相同，这样就形成了镜面对称。

bool judge(struct TreeNode* left,struct TreeNode*right)
{if(left==NULL&&right==NULL){return true;}if(left==NULL||right==NULL){return false;}if(left->val!=right->val){return false;}return judge(left->left,right->right)&&judge(left->right,right->left);
}bool isSymmetric(struct TreeNode* root)
{if(root==NULL){return true;}return judge(root->left,root->right);
}

4. 二叉树的前序遍历

OJ链接

其实这道题就是一个简单的前序遍历，只是把打印换成了将数据存入数组

int TreeSize(struct TreeNode* root)
{/*if (root == NULL){return;}size++;TreeSize(root->left);TreeSize(root->right);*/return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}void preorder(struct TreeNode* root, int* pi,int *a)
{if(root==NULL){return ;}a[(*pi)++]=root->val;preorder(root->left,pi,a);preorder(root->right,pi,a);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{*returnSize=TreeSize(root);int *a =(int *)malloc(sizeof(int)*(*returnSize));int i=0;preorder(root,&i,a);return a;}

5. 另一颗树的子树。

OJ链接

这道题目其实和查找二叉树数值为x的那个函数很像，我们只要看每个子树和右边那个树是否相等即可。

bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{if(p==NULL&&q==NULL){return true;}if(p==NULL||q==NULL){return false;}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)
{if(root==NULL){return false;}if(isSameTree(root,subRoot)){return true;}return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}

6.二叉树的构建及遍历

OJ链接

  因为前序遍历的顺序是：根，左子树，右子树。所以我们在读取他来创建二叉树的时候也是这个顺序，我们先创建根，让根与其左子树和右子树相连，而左子树又可以分为左子树的根与其左子树和右子树相连……以此就构建了递归。这里我们只需要注意最后的结束条件，就是出现#，就返回NULL。

typedef struct BinaryTreeNode {char data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
} BTNode;BTNode *CreatTree(char *a,int *pi)
{if(a[*pi]=='#'){(*pi)++;return NULL;}BTNode*node=(BTNode*)malloc(sizeof(BTNode));node->data=a[(*pi)++];node->left=CreatTree(a, pi);node->right=CreatTree(a, pi);return node;
}void Inorder(BTNode*root)
{if(root==NULL){return;}Inorder(root->left);printf("%c ",root->data);Inorder(root->right);
}
int main() {char a[100];scanf("%s",a);int i=0;BTNode*root=CreatTree(a,&i);Inorder(root);return 0;
}

7.翻转二叉树：

OJ链接

  这是一道很经典的二叉树问题。显然，我们从根节点开始，递归地对树进行遍历，并从叶子节点先开始翻转。如果当前遍历到的节点 root 的左右两棵子树都已经翻转，那么我们只需要交换两棵子树的位置，即可完成以 root 为根节点的整棵子树的翻转。

struct TreeNode* invertTree(struct TreeNode* root)
{if(root==NULL){return NULL;}struct TreeNode* left=invertTree(root->left);struct TreeNode* right=invertTree(root->right);root->left=right;root->right=left;return root;
}

总结

  更新不易，辛苦各位小伙伴们动动小手，👍三连走一走💕💕 ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！

专栏订阅：
每日一题
c语言学习
算法
智力题
初阶数据结构
更新不易，辛苦各位小伙伴们动动小手，👍三连走一走💕💕 ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！