前言
Helllo,今天，博主将要带领大家来深度解析几道经典的二叉树OJ题，来巩固我们前面学过的二叉树知识，我们在进行二叉树练习的时候，还是要对二叉树有较为深入的认识，所以新来的小伙伴，博主强烈推荐可以先去看看博主之前的文章：
http://t.csdnimg.cn/VOQ1S
http://t.csdnimg.cn/dijrW
好，咱们废话不多说，三连上车，咱们开始今天的主题。
1.基础篇
1.1单值二叉树
题目链接：965. 单值二叉树 - 力扣（LeetCode）
这里我们首先来分析一下题意：
我们首先要遍历所有的节点，然后判断所有有效节点的值是不是相等的
根据前面学过的知识，我们明白了二叉树是递归形式的结构。明确了步骤，我们就来实现我们的代码：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isUnivalTree(TreeNode* root) {
if(root == nullptr)
return true;
//在进行值对比时，首席那应当确保的是，节点不为空
if(root->left && root->left->val != root->val)
return false;
if(root->right && root->right->val != root->val)
return false;
return isUnivalTree(root->left) && isUnivalTree(root->right);//左子树和右子树有一边返回false,整个表达式的结果就是false
}
};接下来，我们来测试一下效果：
1.2.相同的树
题目链接：100. 相同的树 - 力扣（LeetCode）
解题思路：
首先比较根节点是否相同，然后分别比较左右子树是否相同，同时结构结构上也要完全一样。
这道题的解题思路其实十分的简单，我们按照上面的思路，来实现我们的代码：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if(q == nullptr && p == nullptr)
return true;
if(q == nullptr || p == nullptr)
return false;
if (q->val != p->val)
return false;
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
};接下来我们来测试一下代码的效果：
1. 3.对称二叉树
题目链接：101. 对称二叉树 - 力扣（LeetCode）
对称二叉树的题目相对于前面的题目就有一些难度了，我们可以看到，判断一颗二叉树是否为对称二叉树，就是要在除根节点外，判断根节点的左右子树是否为轴对称相等，包括结构和数值。这里我们就要巧妙的运用，两颗树相等的方法来判断两颗子树是否对称相等，对称相等其实也就是在进行对比时，将左子树和右子树的节点比较顺序换一下就行。
我们先来实现我们的代码。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isSameTree(TreeNode* q, TreeNode* p)
{
if(q == nullptr && p == nullptr)
return true;
if (q == nullptr || p == nullptr)
return false;
if (p->val != q->val)
return false;
return isSameTree(q->left, p->right) && isSameTree(q->right, p->left);
}//对称相等与两颗子树相等的区别就是，递归比较时节点成对称比较
bool isSymmetric(TreeNode* root) {
if (root == nullptr)
return true;
bool ret = isSameTree(root->left, root->right);
return ret;
}
};我们来测试一下代码的效果：
OK,这里我们就顺利的通过了。
1.4另一颗子树
题目链接：572. 另一棵树的子树 - 力扣（LeetCode）
根据题意，这里我们还是要用到两颗树相等的方法，我们分析完题意就能看出，判断子树的条件相比于判断对称二叉树，就是每一个节点都能够作为根节点，进行相同树的判定:
所以我们就来实现我们的代码：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q)
{
if (p == nullptr && q == nullptr)
return true;
if (q == nullptr || p == nullptr)
return false;
if (q->val != p->val)
return false;
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
if (root == nullptr)
return false;
if (isSameTree(root, subRoot))
{
return true;
}
return (isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot));
}
};接下来我们就来测试一下我们写得代码：
这样我们就完成了这道题。
2.进阶篇
2.1 二叉树的创建和遍历
题目链接：二叉树遍历_牛客题霸_牛客网 (nowcoder.com)
这道题就有一些难度了，我们首先来分析一下题意：
- 1.我们首先要读取一串先序遍历的字符串。
- 2，根据现需遍历的字符串来创建二叉树。
- 3.再重新输出二叉树的后序遍历。
首先我们知道了，二叉树的存储元素为字符串，‘#’代表的是空树。
根据先序遍历的性质我们可以推断出二叉树的形状：
如实例中的字符串： abc##de#g##f###
上面的就是我们经过推断的得到的二叉树结构。
接下来我们来实现代码：
首先我们必须要创建一颗二叉树的基本结构：
class Tree
{
public:
char data;
Tree* left;
Tree* right;
};接下来我们来根据所读取的字符串来创建二叉树：
二叉树的基础结构就是链表，数据结构的关联就是递归：
int main()
{
//读取字符串，字符串的大小不大于100
char arr[100] ;
scanf("%s", arr);
//创建二叉树
int i = 0;
Tree* root = CreatTree(arr,i);
//打印中序遍历
InOrder(root);
return 0;
}先来看看CreatTree函数：
Tree* BuyNode(char data)
{
Tree* root = (Tree*)malloc(sizeof(Tree));
root->data = data;
root->left = root->right = nullptr;
return root;
}
Tree* CreatTree(char* arr, int& pi)//应用引用的知识通过传输实参的拷贝，改变实参
{
if (arr[pi] == '#')
{
pi++;
return nullptr;
}
Tree* root = BuyNode(arr[pi++]);
root->left = CreatTree(arr, pi);
root->right = CreatTree(arr, pi);
return root;
}创建好二叉树后，我们就可以进行中序遍历了，他的实现也是最简单的部分，我们就简单的来看看代码：
void InOrder(Tree* root)
{
if (root == nullptr)
return ;
InOrder(root->left);
cout<<root->data<<" ";
InOrder(root->right);
}
代码我们就写完了：
#include <iostream>
using namespace std;
class Tree
{
public:
char data;
Tree* left;
Tree* right;
};
Tree* BuyNode(char data)
{
Tree* root = (Tree*)malloc(sizeof(Tree));
root->data = data;
root->left = root->right = nullptr;
return root;
}
Tree* CreatTree(char* arr, int& pi)
{
if (arr[pi] == '#')
{
pi++;
return nullptr;
}
Tree* root = BuyNode(arr[pi++]);
root->left = CreatTree(arr, pi);
root->right = CreatTree(arr, pi);
return root;
}
void InOrder(Tree* root)
{
if (root == nullptr)
return ;
InOrder(root->left);
cout<<root->data<<" ";
InOrder(root->right);
}
int main()
{
//读取字符串，字符串的大小不大于100
char arr[100] ;
scanf("%s", arr);
//创建二叉树
int i = 0;
Tree* root = CreatTree(arr,i);
//打印中序遍历
InOrder(root);
return 0;
}接下来我们来展示一下效果：
2.2 前序遍历
相信在看到题目的时候·，大家都是信心满满，但是这道题，并不是大家想的那么简单：
我们首先来看看题意：
根据题目所给的接口函数我们就知道，这道题并不简单：
我们首先拿到的是一个根节点root,和一个整形指针，要返回的是一个整形指针。
由此可知，我们要将前序遍历的结果保存在数组中，最后一数组的形式返回。
接下来我们一步一步的拆解这道题：
- 1.首先我们要得到这可树的节点数
- 2.根据节点数来创建数组。
- 3.前序遍历，将结果保存在数组中。
首先我们来得到这可树的节点数：
typedef struct TreeNode TreeNode;
int CountNode(TreeNode *root)
{
if (root == NULL)
{
return 0;
}
return 1 + CountNode(root->right) + CountNode(root->left);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
//得到二叉树节点的个数
*returnSize = CountNode(root);
}然后我们来申请空间，创建数组：
typedef struct TreeNode TreeNode;
int CountNode(TreeNode *root)
{
if (root == NULL)
{
return 0;
}
return 1 + CountNode(root->right) + CountNode(root->left);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
//得到二叉树节点的个数
*returnSize = CountNode(root);
//创建数组申请空间
int *arr = (int*)malloc(szieod(int) * (*returnSize));
}然后我们就开始前序遍历，这个我们应该很熟悉了，我们快速看看：
typedef struct TreeNode TreeNode;
int CountNode(TreeNode *root)
{
if (root == NULL)
{
return 0;
}
return 1 + CountNode(root->right) + CountNode(root->left);
}
void _preorderTraversal(TreeNode* root, int *arr, int *pi)
{
if (root == NULL)
return;
arr[(*pi)++] = root->val;
_preorderTraversal(root->left, arr, pi);
_preorderTraversal(root->right, arr, pi);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
//得到二叉树节点的个数
*returnSize = CountNode(root);
//创建数组申请空间
int *arr = (int*)malloc(sizeof(int) * (*returnSize));
//前序遍历
int i = 0;
_preorderTraversal(root, arr, &i);
return arr;
}代码到这里就实现完了，我们来测试一下效果，
感兴趣的小伙伴也可以去挑战一下，下面的两道题，这两道题和这道题有异曲同工之妙！！
题目链接：1.. - 力扣（LeetCode）
2.94. 二叉树的中序遍历 - 力扣（LeetCode）
好，今天的学习就到这里，感谢大家的阅读，咱们下期再见。
拜拜！！！
![MyBatis[进阶]](https://i-blog.csdnimg.cn/direct/0d9207b99c99479ead59502dce566bd1.png)
