📙作者简介： 清水加冰，目前大二在读，正在学习C/C++、Python、操作系统、数据库等。
📘相关专栏：C语言初阶、C语言进阶、C语言刷题训练营、数据结构刷题训练营、有感兴趣的可以看一看。
欢迎点赞 👍 收藏 ⭐留言 📝 如有错误还望各路大佬指正！
✨每一次努力都是一种收获，每一次坚持都是一种成长✨
目录
前言
📖题目1：翻转二叉树
📖题目2：相同的树
📖题目3：对称二叉树
📖题目4：另一棵树的子树
📖题目5：二叉树的前序遍历
总结
前言
我们学习了二叉树的顺序结构和链式结构，在日常刷题在，我们最常见的就是链式二叉树，刚学习完链式二叉树刷题上手比较难，本期我将继续开始数据结构刷题专栏，为大家提供二叉树（初阶）相关的练习和力扣OJ的经典题目以及题目讲解，以便于大家更容易上手二叉树部分的刷题。
📖题目1：翻转二叉树
题目描述：
题目链接：
翻转二叉树https://leetcode.cn/problems/invert-binary-tree/description/
✨题目解析：
本道题目较为简单，要学会巧妙运用递归解决问题，翻转二叉树也就是翻转它的左子树和右子树，然后不断的向下分，在使用递归时要注意递归结束的条件，确保所有的控件路径都返回值。
代码如下：
struct TreeNode* invertTree(struct TreeNode* root){
if(root==NULL)
{
return NULL;
}
struct TreeNode* left=invertTree(root->left);
struct TreeNode* right=invertTree(root->right);
root->right=left;
root->left=right;
return root;
}📖题目2：相同的树
题目描述：
题目链接：
相同的树https://leetcode.cn/problems/same-tree/description/
✨题目解析：
这道题目的递归思路比上道题复杂一点，主要考察的是对递归的使用以及控制。题目中传进来的是两个树，那要如何去控制递归呢？
两棵树是否相同，主要就是比较对于位置的节点数据是否相同，如果两棵树的每个对应节点都相等，这两棵树就相等，但单纯的判断值是否相等无法做到所有的控件路径都返回值，这里也要考虑特殊情况，当一颗树为NULL，另一颗树不为空，这时就要返回false，两棵树当前节点都为NULL，就返回true。有了这些前提，我们对代码进行实现，那这样写对不对呢？
bool isSameTree(struct TreeNode* p, struct TreeNode* q){
if(p==NULL&&q==NULL)//两个都为NULL就返回True
{
return true;
}
if(p==NULL||q==NULL)//两棵树都不为NULL为前提
{
return false;
}
if(p->val==q->val)
{
return true;
}
return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}这样写乍一看没什么问题，但它在力扣上通过不了，例如：
p：[1,2] q：[1,null,2]
你会发现它根本就没递归进去就返回了，只比较了根节点的值。我们需要让它递归到最后，也就是叶子节点，从叶子节点开始。既然正向行不通，那就逆向，如果它们的val不相等就返回false。
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);
}这样就可以递归到叶子节点，如果递归到最后一直到叶子节点都没有返回false，那就说明递归路径上的节点都相等，如果有一个返回的是false，最后返回的是左子树与右子树取&&的结果，最终一定会返回false。如果节点都相当才会返回true。
例如这棵树：递归从左子树开始，节点2的left递归返回true，right返回也是true，那节点2整体返回就是true，然后开始递归右子树，右子树返回和左子树一样也是true。然后返回到节点1的递归左右子树都为true，那整体就返回true。
📖题目3：对称二叉树
题目描述：
题目链接：
对称二叉树https://leetcode.cn/problems/symmetric-tree/✨题目解析：
这道题的解法和上道题很像，也就是在上道题做了一点进阶。
它让我们判断对称，那我们就可以将这棵树的左子树和右子树分为两棵树，上道题目判断是相同位置的节点相同，我们传的都是p->left,q->left，我们观察一下对称的二叉树，左子树的左孩子节点与右子树的右孩子节点相同，左子树的右孩子与右子树的左孩子相同。
那我们在判断相同时是否就可以这样传值，去比较左子树的左孩子和右子树的右孩子，左子树的右孩子和右子树的左孩子是否相同。
那我们就只需改变一下传的参数即可。我们套用一下上边相同的二叉树的进行变形一下：
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->right)&&isSameTree(p->right,q->left);
}
bool isSymmetric(struct TreeNode* root){
return isSameTree(root->left,root->right);
}📖题目4：另一棵树的子树
题目链接：
另一棵树的子树https://leetcode.cn/problems/subtree-of-another-tree/description/
✨题目解析：
判断一颗树是否是另一棵树的子树，还是会用到两棵树是否相等。只不过这道题目需要注意一下开始比较的条件。我们先写一个框架
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
if(root==NULL)
{
return false;
}
if(root->val==subRoot->val)
{
//开始比较
……
}
return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
//遍历左子树 // 遍历右子树
}文章来源：https://www.toymoban.com/news/detail-728062.html
如果完整的树为NULL那就不在需要判断了，直接返回false。然后开始比较root的值是否与subRoot的值相等，如果相等就从值相等的节点位置开始判断两棵树是否相同。在寻找相同值的过程中我们需要遍历二叉树，遍历二叉树最简便的方法就是使用递归，只要root左子树或右子树有一个存在子树相同，那就返回true（所以这里使用 “ || ” ）。
注意：只有返回类型为bool类型时才可以进行&&或||的操作
完整代码如下：
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
if(root==NULL)
{
return false;
}
if(root->val==subRoot->val)
{
if(isSameTree(root,subRoot)) //isSameTree函数使用的是上述题目2的代码
{
return true;
}
}
return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}📖题目5：二叉树的前序遍历
题目描述：
题目链接：
二叉树的前序遍历https://leetcode.cn/problems/binary-tree-preorder-traversal/
✨题目解析：
这道二叉树的前序遍历和我们·之前的不太一样，我们需要把遍历的值放在一个数组中，所以首先我们还需要知道二叉树的节点个数才可以创建数组，然后再开始遍历二叉树。
我们可以分两个接口来写：
int* preorderTraversal(struct TreeNode* root, int* returnSize){
*returnSize=0; //返回的数组大小
int n=TreeSize(root);
int* ret=(int*)malloc(sizeof(int)*n);
preorder(root,ret,returnSize);//遍历二叉树
return ret;//返回数组
}这里的前序遍历和之前没什么区别，区别就在原本输出的位置需要把数据存到数组中：
void preorder(struct TreeNode* root,int* arr,int* i)
{
if(root==NULL)
{
return;
}
//前序遍历的顺序：根、左子树、右子树
arr[(*i)++]=root->val;
preorder(root->left,arr,i);
preorder(root->right,arr,i);
}完整代码如下：
int TreeSize(struct TreeNode* root)
{
if(root==NULL)
{
return 0;
}
return TreeSize(root->left)+TreeSize(root->right)+1;
}
void preorder(struct TreeNode* root,int* arr,int* i)
{
if(root==NULL)
{
return;
}
arr[(*i)++]=root->val;
preorder(root->left,arr,i);
preorder(root->right,arr,i);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize){
*returnSize=0;
int n=TreeSize(root);
int* ret=(int*)malloc(sizeof(int)*n);
preorder(root,ret,returnSize);
return ret;
}此外还有中序遍历、后序遍历、大家可以自行练习。
二叉树的中序遍历
二叉树的后序遍历
总结
本期主要的内容是学会二叉树的递归遍历，除此之外二叉树还有层序遍历，层序遍历需要的数据结构更复杂一点，下期我再向大家一一介绍，以上便是本前期全部内容，最后，感谢阅读！文章来源地址https://www.toymoban.com/news/detail-728062.html
到了这里，关于数据结构刷题训练——二叉树篇（一）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
