本站消息

站长简介/公众号

  出租广告位,需要合作请联系站长

+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2024-11(2)

这些二叉树基础OJ题你要是还不会,真的没有大厂敢聘用你!

发布于2021-06-07 20:15     阅读(1013)     评论(0)     点赞(18)     收藏(4)


前几天的文章中我写到了二叉树的操作实现,但是一直都没有机会来自己刷刷OJ,今天他来了,准备了好几道题来供大家参考,加固一下我的知识顺便来巩固一下大家的理解,是不是一举两得呢?时间有限,我就不画图展示了,你们这么聪明一定可以看懂的对吧,大概的实现思路我会留在代码处,必要的朋友可以联系我一起讨论啊!

往下看,干货都在下面~在这里插入图片描述

1.单值二叉树

如果二叉树每个节点都具有相同的值,那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时,才返回 true;否则返回 false。
在这里插入图片描述
提示:
给定树的节点数范围是 [1, 100]。
每个节点的值都是整数,范围为 [0, 99] 。

//用递归来实现
//val值与root->val值相等即为真
bool _isUnivalTree(struct TreeNode* root,int val){
    if(root == NULL)
        return true;
    if(val != root->val)
        return false;
    return _isUnivalTree(root->left,val) &&
           _isUnivalTree(root->right,val);
}
bool isUnivalTree(struct TreeNode* root){
    return _isUnivalTree(root,root->val);
}

在这里插入图片描述

2.求二叉树的最大深度

给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点
在这里插入图片描述

int maxDepth(struct TreeNode* root){
    //判空
    if(root == NULL)
        return 0;
    //不为空,则高度即为左右子树较大者+1
    int left = maxDepth(root->left);
    int right = maxDepth(root->right);
    return left > right ? left+1 : right+1;
}

在这里插入图片描述

3.判断是否为相同的树

给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
在这里插入图片描述

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    //两棵树都为空
    if(p == NULL && q == NULL)
        return true;
    //有一棵树为空
    if(p == NULL || q == NULL)
        return false;
    //都不为空,判断两棵树相同位置的节点值是否相等、左右孩子的节点是否相同
    return p->val ==q->val &&
    isSameTree(p->left,q->left) &&
    isSameTree(p->right,q->right);
}

在这里插入图片描述

4.翻转二叉树

翻转一棵二叉树。
在这里插入图片描述

struct TreeNode* invertTree(struct TreeNode* root){
    //判空
    if(root == NULL)
        return NULL;
    //交换根节点的左右子节点
    struct TreeNode* tmp = root->left;
    root->left = root->right;
    root->right = tmp;
    //递归向下直到全部交换
    invertTree(root->left);
    invertTree(root->right);
    return root;
}

在这里插入图片描述

5.对称二叉树

给定一个二叉树,检查它是否是镜像对称的。
在这里插入图片描述

//这个问题可以这样实现
//可以把这颗树拷贝一份,然后递归比较根节点和左右子树,如果都相同则对称
bool _isSymmetric(struct TreeNode* root1,struct TreeNode* root2)
{
	//都为空则对称
    if(root1 == NULL && root2 ==NULL)
    return true;
    //有一个为空,不对称
    if(root1 == NULL || root2 ==NULL)
    return false;
    //递归比较左子树和右子树,都满足则对称
    return root1->val==root2->val &&
     _isSymmetric(root1->right,root2->left) &&
    _isSymmetric(root1->left,root2->right);
}
bool isSymmetric(struct TreeNode* root){
    return _isSymmetric(root,root);
}

在这里插入图片描述

6.另一棵树的子树

给定两个非空二叉树 s 和 t,检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
在这里插入图片描述

bool equal(struct TreeNode* s,struct TreeNode* t)
{
    //首先比较根节点,若根节点同时为空,则两树相等。
    //若其中一个为空,另一个非空,则两树不等。
    //若节点上的数值不等,则两树不等。    
    if(!s &&!t)
        return true;
    if(s == NULL || t == NULL)
        return false;
    if(s->val != t->val)
        return false;
    //节点上的数值相等,进而要向下比较它们的子树是否相等,使用递归,分别比较左右子树是否相等,注意:一定要都相等才可以。
    return s->val == t->val &&
    equal(s->left,t->left) &&
    equal(s->right,t->right);
}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
    //递归到最后,root都已经为空了,那么再无相等可言,return false;
    if(!root)
        return false;
    //选择往那边走
    return equal(root,subRoot)||isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}

7.判断是否为平衡二叉树

给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
在这里插入图片描述在这里插入图片描述

 //先求出该树的深度(层数)
int height(struct TreeNode* root)
{
    if(root == NULL)
    { 
        return 0;
    }
    int left = height(root->left);
    int right =  height(root->right);
    return left > right ? left+1 : right+1;
}
//自顶向下,递归
bool isBalanced(struct TreeNode* root){
    //空树是平衡二叉树
    if(root == NULL)
    {
        return true;
    }
    //三个条件都满足即可
    //其根节点的左右子树的高度差不超过1,然后递归往下走
    return fabs(height(root->left) - height(root->right)) <=1 &&
    isBalanced(root->left) &&isBalanced(root->right);
}

8.二叉树的遍历

编一个程序,读入用户输入的一串先序遍历字符串,根据此字符串建立一个二叉树(以指针方式存储)。 例如如下的先序遍历字符串: ABC##DE#G##F### 其中“#”表示的是空格,空格字符代表空树。建立起此二叉树以后,再对二叉树进行中序遍历,输出遍历结果。

输入描述:
输入包括1行字符串,长度不超过100。
输出描述
可能有多组测试数据,对于每组数据, 输出将输入字符串建立二叉树后中序遍历的序列,每个字符后面都有一个空格。 每个输出结果占一行。
在这里插入图片描述

#include<stdio.h>
#include<assert.h>
#include<malloc.h>
#include<string.h>
 
typedef struct TreeNode
{
    char data;
    struct TreeNode* left;
    struct TreeNode* right;
}TreeNode;
 
//开辟内存
TreeNode* BuyTreeNode(char ch)
{
    TreeNode* node=(TreeNode*) malloc(sizeof(TreeNode));
    if(node == NULL)
    {
        return NULL;
    }
 
    node->data = ch;
    node->left = node->right = NULL;
    return node;
}
 
//创建树
TreeNode* TreeNodeCreate(char arr[],int size,int *index)
{
    TreeNode* root = NULL;
    if(*index < size && '#' != arr[*index])//index小于size并且arr[*index]不等于’#‘
    {
        root = BuyTreeNode(arr[*index]);//创建根节点
        //数组往后走创建左子树
        (*index)++;
        root->left = TreeNodeCreate(arr, size, index);
        //数组往后走创建右子树
        (*index)++;
        root->right = TreeNodeCreate(arr, size, index);
    }
    return root;
}
 
//中序遍历
void InorderTreeNode(TreeNode* root)
{
    if(root == NULL)
        return;
    InorderTreeNode(root->left);
    printf("%c ",root->data);
    InorderTreeNode(root->right);
}
 
//销毁树
void DestroyTree(TreeNode** root)
{
    if(*root)
    {
        DestroyTree(&(*root)->left);
        DestroyTree(&(*root)->right);
        free(*root);
        (*root) = NULL;
    }
  
}
 
int main()
{
    char arr[100];
    //多组输入
    while(scanf("%s",arr) != EOF)
    {
        int index = 0;
        TreeNode* root = TreeNodeCreate(arr,strlen(arr),&index);
        InorderTreeNode(root);
        printf("\n");
        DestroyTree(&root);
    }
    return 0;
}

以上就是本篇文章的重点,今天就到此结束了哈,有不同的观点或者有不同思路的朋友欢迎大家赏光私我哈,本着相互进步的原则,希望大家能多多向我提意见,谢谢~~
在这里插入图片描述



所属网站分类: 技术文章 > 博客

作者:bbjbbh

链接:http://www.phpheidong.com/blog/article/89479/fe1ad3029c12dca791fe/

来源:php黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

18 0
收藏该文
已收藏

评论内容:(最多支持255个字符)