前言
二叉树的OJ题目还是比较有难度的，这篇文章将从易到难为你介绍这些题目，并且给出解析
单值二叉树
- 题目链接
- 具体思路
这道题解释一下就是，确认二叉树中是否有不一样的值，既然要确实是否有不一样的值，我们可以先将根的值提出来，然后再将根与其他的子节点进行比较，这里就要用到前序遍历二叉树的思路
当然，光有前序遍历的思路是不够的，我们还要找到递归结束的条件：
1.找到了不同的值，返回false
2.访问到了空节点，说明之前的节点都是符合条件的，返回true
我们要返回的就是左子树和右子树是否都符合条件，所以要用 &&
- 具体实现如下
typedef struct TreeNode node;
bool judge(node* root, int x)
{
if(root == NULL)
{
return true;
}
if(root->val != x)
{
return false;
}
return judge(root->left, x) && judge(root->right, x);
}
bool isUnivalTree(struct TreeNode* root) {
int x = root->val;
return judge(root, x);
}二叉树的最大深度
- 题目链接
- 题目思路
其实与前面二叉树的实现中求二叉树高度是一个意思，这里就不多讲了，不太懂的可以看这篇文章：
- 具体实现如下
int maxDepth(struct TreeNode* root) {
if(root == NULL)
{
return 0;
}
if(root->left == NULL && root->right == NULL)
{
return 1;
}
int left = maxDepth(root->left);
int right = maxDepth(root->right);
return left > right ? left + 1 : right + 1;
}二叉树的前序遍历
- 题目链接
- 具体思路
首先我们根据题目可以知道，这道题不像我们之前实现的前序遍历，只是单纯的将根打印出来，而是要将每个根按照前序来存在新的数组里面，然后遇到空节点就不存了
所以我们还要单独建一个存数组的函数，首先我们就要清楚我们要放什么形参进去，首先第一个肯定是要一个数组，然后第二个就是二叉树，但是最重要的是我们需要一个形参来代表数组的下标，而这个下标是要跟着函数变化的，因为这是在递归函数里实现，所以我们应该给这个形参的类型设置为指针
接下来我们来实现这个存数组的函数，首先是结束的条件，当访问到空指针是就直接返回，不是空指针就存数据，存完数据后按照前序的方式继续存数据
具体实现如下：
void creatnum(node* root,int* arr, int* i)
{
if(root == NULL)
{
return;
}
arr[(*i)++] = root->val;
creatnum(root->left, arr, i);
creatnum(root->right, arr, i);
}不仅如此，我们在主函数中也要创建合适的数组才能进行传参，所以我们要先计算出总节点的个数，这里就不过多赘述了，已经在二叉树的实现这篇文章中详细讲过了，获得节点个数后使用malloc创建数组就可以了，最后我们再将这个数组传回去就可以了
- 具体实现如下
typedef struct TreeNode node;
int Treesize(node* root)
{
if(root == NULL)
{
return 0;
}
return Treesize(root->left) + Treesize(root->right) + 1;
}
void creatnum(node* root,int* arr, int* i)
{
if(root == NULL)
{
return;
}
arr[(*i)++] = root->val;
creatnum(root->left, arr, i);
creatnum(root->right, arr, i);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
//先算节点个数
int n = Treesize(root);
//创建数组
int* arr = (int*)malloc(sizeof(int) * n);
int i = 0;
//给数组赋值
creatnum(root, arr, &i);
*returnSize = i;
return arr;
}相同的树
- 题目链接
- 具体思路
这道题目最重要的就是搞清楚递归结束的条件，首先我们最先思考的就是访问到两个树对应节点大小不一样时返回false，访问到空指针时也要返回，但是具体要返回什么呢，下面列出几种情况：
1.两个都为空节点：说明已经将可以访问的都访问完了，所以返回true
2.只有一个是空节点，另一个不是：说明两个树不相同，应该返回false
搞清楚递归结束条件后，我们就要清楚返回的形式，也是要运用到左子树和右子树的关系，将两个子树是否相同的问题转化成他们的左子树和右子树是否相同的形式，然后不断递归就可以了
- 具体实现如下
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
if(p == NULL && q == NULL)
{
return true;
}
if(p == NULL)
{
return false;
}
if(q == NULL)
{
return false;
}
if(p->val != q->val)
{
return false;
}
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}对称二叉树
- 题目链接
- 具体思路
其实这一题可以转化为二叉树的左子树和右子树是否是对称子树，也就是将 左子树的右子树 与 右子树的左子树进行比较， 左子树的左子树 与 右子树的右子树 进行比较是否相等，也就是把他们镜像翻转一下来比较，这里就要运用到相同二叉树的知识了，只不过将递归函数中的递归函数的形参改变一下方向而已
- 具体实现如下
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) {
return judge(root->left, root->right);
}另一棵子树
- 题目链接
- 具体思路
这里我们也要使用相同的树的思路，首先我们要用前序遍历找到主树里的所有节点，当访问到的节点对应的数据与子树的数据相同时，就将这个节点与子树进行比较，如果比较相同就返回true，如果比较失败了就不返回，继续比较下一个节点
当我们访问到空节点时就证明之前的所有节点都无法与子树进行匹配，所以就返回false
而我们只要左子树和右子树中有一个子树中存在与此子树能匹配的节点就可以了，所以我们返回用的是 || 的符号
- 具体实现如下
bool issametree(struct TreeNode* root1, struct TreeNode* root2)
{
if(root1 == NULL && root2 == NULL)
{
return true;
}
if(root1 == NULL || root2 == NULL)
{
return false;
}
if(root1->val != root2->val)
{
return false;
}
return issametree(root1->left, root2->left) && issametree(root1->right, root2->right);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
if(root == NULL)
{
return false;
}
if(root->val == subRoot->val)
{
bool a = issametree(root, subRoot);
if(a == true)
{
return a;
}
}
return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}二叉树的构建及遍历
- 题目链接
- 题目要求
- 具体思路
这里不只是单纯的遍历一个二叉树然后构建数组返回，而是要根据一个数组来创建二叉树，但是同样也要遍历这个数组，所以也要用到之前传指针整数的技巧，我们这里先实现创建二叉树的函数
因为是使用前序遍历创建，毎访问到一个不是‘#’的数据就创建一个新节点，然后再给它的左节点和右节点赋值，如果访问到‘#’时就返回NULL，当左节点和右节点都赋值完成时，就返回这个创建的新节点
- 具体实现如下：
//创立新节点
Node* BuyNewnode(DataType x)
{
Node* new = (Node*)malloc(sizeof(Node));
new->val = x;
new->left = new->right = NULL;
return new;
}
//先序建立二叉树(i为下标， n为数组大小)
Node* CreatTree(DataType* arr, int* i)
{
if(arr[*i] == '#')
{
(*i)++;
return NULL;
}
Node* newnode = BuyNewnode(arr[(*i)++]);
newnode->left = CreatTree(arr, i);
newnode->right = CreatTree(arr, i);
return newnode;
}而后面的中序遍历二叉树，只是将二叉树按照中序遍历打印一遍就可以了，没什么太多说的
- 整个函数具体实现如下
#include <stdio.h>
#include <stdlib.h>
typedef char DataType;
typedef struct TreeNode
{
DataType val;
struct TreeNode* left;
struct TreeNode* right;
}Node;
//创立新节点
Node* BuyNewnode(DataType x)
{
Node* new = (Node*)malloc(sizeof(Node));
new->val = x;
new->left = new->right = NULL;
return new;
}
//先序建立二叉树(i为下标， n为数组大小)
Node* CreatTree(DataType* arr, int* i)
{
if(arr[*i] == '#')
{
(*i)++;
return NULL;
}
Node* newnode = BuyNewnode(arr[(*i)++]);
newnode->left = CreatTree(arr, i);
newnode->right = CreatTree(arr, i);
return newnode;
}
void print(Node* root)
{
if(root == NULL)
{
return;
}
print(root->left);
printf("%c ", root->val);
print(root->right);
}
int main() {
char arr[10000];
scanf("%s", arr);
int i = 0;
Node* new = CreatTree(arr, &i);
print(new);
return 0;
}总结
至此，二叉树的基本OJ题就已经讲解完了，希望能对你有帮助！
ps：今天博客的图片全部丢失了，气死我了
评论（0）
暂无评论