【数据结构和算法】二叉树基础oj练习

2022-05-03 10:50:29

二叉树

1. 单值二叉树

1.判断根的左孩子的值与根结点是否相同。
2.判断根的右孩子的值与根结点是否相同。
3.判断以根的左孩子为根的二叉树是否是单值二叉树。
4.判断以根的右孩子为根的二叉树是否是单值二叉树。若满足以上情况，则是单值二叉树。

注：空树也是单值二叉树。

代码：

/**
 * 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==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);//左子树是单值二叉树并且右子树是单值二叉树（递归）
    }
};

2.检查两颗树是否相同

–oj链接

题解：
判断两棵二叉树是否相同，也可以将其分解为子问题：

1.比较两棵树的根是否相同。
2.比较两根的左子树是否相同。
3.比较两根的右子树是否相同。

代码：

//判断两棵二叉树是否相同
bool isSameTree(BTNode* p, BTNode* q)
{
	if (p == NULL&&q == NULL)//两棵树均为空，则相同
		return true;
	if (p == NULL || q == NULL)//两棵树中只有一棵树为空，则不相同
		return false;
	if (p->data != q->data)//两棵树根的值不同，则不相同
		return false;
	return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);//两棵树的左子树相同并且右子树相同，则这两棵树相同
}

3.对称二叉树

–oj链接

题解：
要判断某二叉树是否是对称二叉树，则判断其根结点的左子树和右子树是否是镜像对称即可。若在遍历过程中发现镜像对称的某两个结点值不同，则无需继续遍历。

代码：

//判断镜像位置是否相等
bool travel(BTNode* root1, BTNode* root2)
{
	if (root1 == NULL&&root2 == NULL)//红蓝轨迹同时遍历到NULL，函数返回
		return true;
	if (root1 == NULL || root2== NULL)//红蓝指针中，一个为NULL，另一个不为NULL，即镜像不相等
		return false;
	if (root1->val!= root2->val)//红蓝指针指向的结点值不同，即镜像不相等
		return false;
	//子问题：左子树遍历顺序：先左后右，右子树遍历顺序：先右后左。若两次遍历均成功，则是对称二叉树
	return travel(root1->left, root2->right) && travel(root1->right, root2->left);
}
//对称二叉树
bool isSymmetric(BTNode* root)
{
	if (root == NULL)//空树是对称二叉树
		return true;
	return travel(root->left, root->right);//判断镜像位置是否相等
}

4.另一颗树的子树

–oj链接

题解：
思路：

一个树是另一个树的子树则要么这两个树相等，要么这个树是左树的子树，要么这个树的右树的子树。

用两层递归来实现：
isSameTree函数用于递归检查需要判断的树对应结点是否相同（即判断相同二叉树）；
isSubtree函数则用于判断subRoot 是否为root的子树；

代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
//检验这两棵树是否相同
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);


}
//判断subRoot  是否为root的子树
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
if(root==NULL)//空树，不可能是与subRoot相同（subRoot非空）
return false;
if(isSameTree(root,subRoot))//以root和subRoot为根，开始比较两棵树是否相同
return true;
//判断root的左孩子和右孩子中是否有某一棵子树与subRoot相同
return isSubtree(root->left,subRoot)||
    isSubtree(root->right,subRoot);
}

5.二叉树的构建及遍历

–oj链接

题解：
根据前序遍历所得到的字符串，我们可以很容易地将其对应的二叉树画出来：

我们可以依次从字符串读取字符：

1.若该字符不是#，则我们先构建该值的结点，然后递归构建其左子树和右子树。
2.若该字符是#，则说明该位置之下不能再构建结点了，返回即可。

构建完树后，使用中序遍历打印二叉树的数据即可。

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode
{
    struct TreeNode* left;
    struct TreeNode* right;
    char data;
}TreeNode;
//创建树
TreeNode* CreateTree(char* str, int* pi)
{
    if(str[*pi] == '#')//
    {
        (*pi)++;
        return NULL;
    }
    //不是NULL，构建结点
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    
    root->data = str[*pi];
    (*pi)++;
    //递归构建左子树
    root->left = CreateTree(str, pi);
    //递归构建右子树
    root->right = CreateTree(str, pi);
    return root;
}
//中序遍历
void Inorder(TreeNode* root)
{
    if(root == NULL)
        return;
    Inorder(root->left);
    printf("%c ", root->data);
    Inorder(root->right);
}
int main()
{
    char str[100];
    scanf("%s", str);
    int i = 0;
    TreeNode* root = CreateTree(str, &i);
    Inorder(root);
    return 0;
}

6.二叉树的前序遍历

–oj链接

题解：

前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前

思路：
1.首先计算二叉树中结点的个数，便于确定动态开辟的数组的大小。
2.遍历二叉树，将遍历结果存储到数组中。
3.返回数组。
代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

int TreeSize(struct TreeNode* root)//求树的结点个数
{
    if(root==NULL)
    return 0;
    return TreeSize(root->left)+TreeSize(root->right)+1;
}
void _preorderTraversal(struct 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=TreeSize(root);
    int *arr=malloc(sizeof(int)* *returnSize);
    int i=0;
    _preorderTraversal(root,arr,&i);

    return arr;
}

中序和后序遍历原理差不多，只在递归顺序有差别

7.二叉树的中序遍历

–oj链接

代码：

//求树的结点个数
int TreeSize(struct TreeNode* root)
{
	return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
//将树中结点的值放入数组
void inorder(struct TreeNode* root, int* arr, int* pi)
{
    //中序遍历
	if (root == NULL)//根结点为空，直接返回
		return;
	inorder(root->left, arr, pi);//先将左子树中结点的值放入数组
	arr[(*pi)++] = root->val;//再将根结点的值放入数组
	inorder(root->right, arr, pi);//最后将右子树中结点的值放入数组
}

int* inorderTraversal(struct TreeNode* root, int* returnSize)
{
	*returnSize = TreeSize(root);//值的个数等于结点的个数
	int* arr = (int*)malloc(sizeof(int)*(*returnSize));
	int i = 0;
	inorder(root, arr, &i);//将树中结点的值放入数组
	return arr;
}

8.二叉树的后序遍历

–oj链接
代码：

int TreeSize(struct TreeNode* root)
{
	return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
//将树中结点的值放入数组
void postorder(struct TreeNode* root, int* arr, int* pi)
{
    //后序遍历
	if (root == NULL)//根结点为空，直接返回
		return;
	postorder(root->left, arr, pi);//先将左子树中结点的值放入数组
	postorder(root->right, arr, pi);//最后将右子树中结点的值放入数组
    arr[(*pi)++] = root->val;//再将根结点的值放入数组
}
int* postorderTraversal(struct TreeNode* root, int* returnSize){
*returnSize = TreeSize(root);//值的个数等于结点的个数
	int* arr = (int*)malloc(sizeof(int)*(*returnSize));
	int i = 0;
	postorder(root, arr, &i);//将树中结点的值放入数组
	return arr;
}

码农公寓

二叉树

1. 单值二叉树

2.检查两颗树是否相同

3.对称二叉树

4.另一颗树的子树

5.二叉树的构建及遍历

6.二叉树的前序遍历

7.二叉树的中序遍历

8.二叉树的后序遍历

相关文章