前言
我们学习了二叉树的顺序结构和链式结构，在日常刷题在，我们最常见的就是链式二叉树，刚学习完链式二叉树刷题上手比较难，本期我将继续开始数据结构刷题专栏，为大家提供二叉树（初阶）相关的练习和力扣OJ的经典题目以及题目讲解，以便于大家更容易上手二叉树部分的刷题。
📖题目1：翻转二叉树
题目描述：
题目链接：
✨题目解析：
本道题目较为简单，要学会巧妙运用递归解决问题，翻转二叉树也就是翻转它的左子树和右子树，然后不断的向下分，在使用递归时要注意递归结束的条件，确保所有的控件路径都返回值。
代码如下：
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：相同的树
题目描述：
题目链接：
✨题目解析：
这道题目的递归思路比上道题复杂一点，主要考察的是对递归的使用以及控制。题目中传进来的是两个树，那要如何去控制递归呢？
两棵树是否相同，主要就是比较对于位置的节点数据是否相同，如果两棵树的每个对应节点都相等，这两棵树就相等，但单纯的判断值是否相等无法做到所有的控件路径都返回值，这里也要考虑特殊情况，当一颗树为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：对称二叉树
题目描述：
题目链接：
✨题目解析：
这道题的解法和上道题很像，也就是在上道题做了一点进阶。
它让我们判断对称，那我们就可以将这棵树的左子树和右子树分为两棵树，上道题目判断是相同位置的节点相同，我们传的都是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：另一棵树的子树
题目链接：
✨题目解析：
判断一颗树是否是另一棵树的子树，还是会用到两棵树是否相等。只不过这道题目需要注意一下开始比较的条件。我们先写一个框架
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); //遍历左子树 // 遍历右子树 }
如果完整的树为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：二叉树的前序遍历
题目描述：
题目链接：
✨题目解析：
这道二叉树的前序遍历和我们·之前的不太一样，我们需要把遍历的值放在一个数组中，所以首先我们还需要知道二叉树的节点个数才可以创建数组，然后再开始遍历二叉树。
我们可以分两个接口来写：
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; }
此外还有中序遍历、后序遍历、大家可以自行练习。
总结
本期主要的内容是学会二叉树的递归遍历，除此之外二叉树还有层序遍历，层序遍历需要的数据结构更复杂一点，下期我再向大家一一介绍，以上便是本前期全部内容，最后，感谢阅读！
