【数据结构】二叉树相关OJ题
文章目录
一、单值二叉树
题目链接
题目描述
如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时，才返回 true；否则返回 false。
思路分析
递归解决：先比较根节点和两个子节点的val，如果不相等就返回false，相等就返回true，然后递归比较左子树和右子树。
代码实现
bool isUnivalTree(struct TreeNode* root){
if(root == NULL)
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);
}
image-20220815174450240
二、相同的树
题目链接
题目描述
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
image-20220815174626557
思路分析
递归解决：比较两棵树根节点的val是否相同，在递归比较左右子树节点的val是否相同。
代码实现
//思路：检查节点的值或者节点的数量是否相同，如果不同直接返回false，然后递归检查左右子树是否相同
bool isSameTree(struct TreeNode* p, struct TreeNode* q){
if(p == NULL && q == NULL)
return true;
if(p == NULL || q == NULL) //当两棵树中只有一棵树的节点为空时，节点数量不相同时，直接返回false
return false;
//检查节点和值是否相同
if(p->val != q->val)
return false;
//检查左右子树是否相同
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
image-20220815174818881
三、对称二叉树
题目链接
题目描述
给你一个二叉树的根节点 root ， 检查它是否轴对称。
image-20220815175011206
思路分析
这道题是上面那道题的一个简单变形，二者在实现思路上大致一样，只是细节上有所不同而已。
由于对称结构是最左边和最右边的节点相同，所以我们需要对 检查两棵子树是否对称 的代码中递归的参数进行调整：
return isSameTree(p->left, q->right) && isSameTree(p->right, q->left);代码实现
//检查两棵子树是否对称
bool isSameTree(struct TreeNode* p, struct TreeNode* q){
if(p == NULL && q == NULL)
return true;
if(p == NULL || q == NULL) //当两棵树中只有一棵树的节点为空时，节点数量不相同时，直接返回false
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);
}
image-20220815175259657
四、二叉树的前序遍历
题目链接
题目描述
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
思路分析
二叉树的前序遍历在前面我们已经学过，只是这里有两点需要注意的地方：
1、由于二叉树的节点数数未知的，为了不浪费空间，我们可以先求出二叉树的节点数，然后再开辟对应大小的空间；
2、由于数据是存储在一个数组中，所以我们需要一个变量 i 来控制数组的下标；同时，由于在递归调用过程中对形参的改变不会影响实参，所以这里我们需要传递 i 的地址，通过指针来控制 i 的增长。
代码实现
// 二叉树节点个数
int BinaryTreeSize(struct TreeNode* root)
{
if (root == NULL)
return 0;
//左子树节点个数+右子树节点个数+根节点
return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
// 二叉树前序遍历
void BinaryTreePrevOrder(struct TreeNode* root, int* ret, int* pi)
{
if (root == NULL)
{
return;
}
//先访问根，再访问左子树，最后访问右子树
ret[*pi] = root->val;
(*pi)++;
BinaryTreePrevOrder(root->left, ret, pi);
BinaryTreePrevOrder(root->right, ret, pi);
}
//思路：求出二叉树的节点个数，然后malloc等长的数组来存储节点值，最后通过前序遍历将节点值放入数组中
int* preorderTraversal(struct TreeNode* root, int* returnSize){
//求二叉树节点个数
int n = BinaryTreeSize(root);
int* ret = (int*)malloc(sizeof(struct TreeNode)*n);
//前序遍历
int i = 0;
BinaryTreePrevOrder(root, ret, &i);
*returnSize = i;
return ret;
}
image-20220815180127544
五、二叉树的中序遍历
题目链接
题目描述
给定一个二叉树的根节点 root ，返回它的 中序 遍历* 。
思路分析
前序遍历和中序遍历基本上是一样的，只是访问顺序改变而已。
代码实现
// 二叉树节点个数
int BinaryTreeSize(struct TreeNode* root)
{
if (root == NULL)
return 0;
//左子树节点个数+右子树节点个数+根节点
return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
// 二叉树中序遍历
void BinaryTreeInOrder(struct TreeNode* root, int* ret, int* pi)
{
if (root == NULL)
{
return;
}
//先访问左子树，再访问根，最后访问右子树
BinaryTreeInOrder(root->left, ret, pi);
ret[*pi] = root->val;
(*pi)++;
BinaryTreeInOrder(root->right, ret, pi);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize){
//求二叉树节点个数
int n = BinaryTreeSize(root);
int* ret = (int*)malloc(sizeof(struct TreeNode)*n);
//前序遍历
int i = 0;
BinaryTreeInOrder(root, ret, &i);
*returnSize = i;
return ret;
}
image-20220815180411693
六、二叉树的后序遍历
题目链接
题目描述
给定一个二叉树的根节点 root ，返回它的 后序 遍历 。
思路分析
后序遍历和前序、中序遍历基本上是一样的，只是访问顺序改变而已。
代码实现
// 二叉树节点个数
int BinaryTreeSize(struct TreeNode* root)
{
if (root == NULL)
return 0;
//左子树节点个数+右子树节点个数+根节点
return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
// 二叉树前序遍历
void BinaryTreePostOrder(struct TreeNode* root, int* ret, int* pi)
{
if (root == NULL)
{
return;
}
//先访问根，再访问左子树，最后访问右子树
BinaryTreePostOrder(root->left, ret, pi);
BinaryTreePostOrder(root->right, ret, pi);
ret[*pi] = root->val;
(*pi)++;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize){
//求二叉树节点个数
int n = BinaryTreeSize(root);
int* ret = (int*)malloc(sizeof(struct TreeNode)*n);
//前序遍历
int i = 0;
BinaryTreePostOrder(root, ret, &i);
*returnSize = i;
return ret;
}
image-20220815180527829
七、另一棵树的子树
题目链接
题目描述
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
image-20220815180715937
思路分析
由于root 和 subRoot 中可能含有一个或多个值相同的节点，所以我们只能遍历root，取出其中的每一个节点与subRoot进行比较，看是否相同。
代码实现
//思路：检查节点的值或者节点的数量是否相同，如果不同直接返回false，然后递归检查左右子树是否相同
bool isSameTree(struct TreeNode* p, struct TreeNode* q){
if(p == NULL && q == NULL)
return true;
if(p == NULL || q == NULL) //当两棵树中只有一棵树的节点为空时，节点数量不相同时，直接返回false
return false;
//检查节点和值是否相同
if(p->val != q->val)
return false;
//检查左右子树是否相同
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
//思路：遍历root，取root的每一棵子树与sunroot比较，如果相同，就返回true
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);
}
image-20220815180950041
九、二叉树构建及遍历
题目链接
题目描述
编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
示例1
输入：abc##de#g##f###
输出：c b e g d f a 思路分析
这道题就是把二叉树的构建和二叉树的遍历结合到了一起而已，我们分别完全这两个功能即可。
代码实现
#include <stdio.h>
#include <stdlib.h>
//符号和结构的定义
typedef char BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
//构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int* pi)
{
if (a[*pi] == '#')
{
(*pi)++;
return NULL;
}
//创建根节点
BTNode* root = (BTNode*)malloc(sizeof(BTNode));
if (root == NULL)
{
perror("malloc fail");
exit(-1);
}
root->data = a[*pi];
(*pi)++;
//创建左右子树
root->left = BinaryTreeCreate(a, pi);
root->right = BinaryTreeCreate(a, pi);
return root;
}
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
//先访问左子树，再访问根，最后访问右子树
BinaryTreeInOrder(root->left);
printf("%c ", root->data);
BinaryTreeInOrder(root->right);
}
int main()
{
char arr[100];
scanf("%s", arr);
//构建二叉树
int i = 0;
BTNode* root = BinaryTreeCreate(arr, &i);
//二叉树的中序遍历
BinaryTreeInOrder(root);
return 0;
}
image-20220815181321541
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-08-17，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
