二叉树在线OJ

简介: 二叉树在线OJ
二叉树的构建及遍历

本题目的要求是:

输入一个数组,里面存放了若干个字符,#代表了空指针,数组中的顺序是

是先序遍历,然后要求你用中序输出

首先我们要做的就是构造结构体:

typedef struct TreeNode
{
    char val;
    struct TreeNode* left;
    struct TreeNode* right;
}TreeNode;

然后用先序遍历构造二叉树

当数组的首元素为#或者“\0”,即二叉树没有根节点,为空树,直接接返回

然后我们开辟新节点的空间

然后进行先序遍历构造二叉树:

首先将newnode的值置为数组首元素,同时下标count++

然后递归newnode的左子树根节点,*(count)++(count传的是地址,所以记得解引用),随后递归右子树根节点即可,最后返回newnode,就是二叉树的根节点

TreeNode* maketree(char*arr,int*count)
{
    if(arr[*count]=='#'||arr[*count]=='\0')
    {
        return NULL;
    }
    TreeNode* newnode = (TreeNode*)malloc(sizeof(TreeNode));
    newnode->val = arr[(*count)++];
    newnode->left = maketree(arr,count);
    (*count)++;
    newnode->right = maketree(arr,count);
    return newnode;
}

最后写一个中序遍历的输出:

void Inorder(TreeNode* root)
{
    if(root==NULL)
    {
        return;
    }
    Inorder(root->left);
    printf("%c ",root->val);
    Inorder(root->right);
}

完整代码如下:

#include <stdio.h>
#include<stdlib.h>
typedef struct TreeNode
{
    char val;
    struct TreeNode* left;
    struct TreeNode* right;
}TreeNode;
TreeNode* maketree(char*arr,int*count)
{
    if(arr[*count]=='#'||arr[*count]=='\0')
    {
        return NULL;
    }
    TreeNode* newnode = (TreeNode*)malloc(sizeof(TreeNode));
    newnode->val = arr[(*count)++];
    newnode->left = maketree(arr,count);
    (*count)++;
    newnode->right = maketree(arr,count);
    return newnode;
}
void Inorder(TreeNode* root)
{
    if(root==NULL)
    {
        return;
    }
    Inorder(root->left);
    printf("%c ",root->val);
    Inorder(root->right);
}
 
int main()
{
    char arr[101];
    scanf("%s",arr);
    int count = 0;
    TreeNode* tree = maketree(arr,&count);
    Inorder(tree);
    return 0;
}
判断一颗二叉树是否是平衡二叉树

本题很简单了:

直接判断左子树和右子树的高度的绝对值是否小于等于1即可

同时左子树的子树和右子树的子树也要同时递归

调用求二叉树高度的函数

int height(struct TreeNode* root)
{
    if(root==NULL)
    {
        return 0;
    }
    return fmax(height(root->left),height(root->right))+1;
}
bool isBalanced(struct TreeNode* root) 
{
    if(root==NULL)
    {
        return true;
    }
    return fabs(height(root->left) - height(root->right)) <= 1 
    && isBalanced(root->left) && isBalanced(root->right);
}
另一颗树的子树

本题就是判断一颗树的子树是否是另一棵树

所以我们首先要做的就是构造一个判断两棵树是否相等的函数:

当两个树同时为空时也是相等的

当其中一个为空时肯定时不想同的

当root的值不等于subroot的值时肯定是不相等的

bool issame(struct TreeNode* root,struct TreeNode* subroot)
{
    if(root==NULL&&subroot==NULL)
        return true;
    if(root==NULL||subroot==NULL)
        return false;
    if(root->val==subroot->val)
    {
        if(issame(root->left,subroot->left)
    &&issame(root->right,subroot->right))
            return true;
    }
    return false;
}

然后调用这个函数:

当root和subroot相等时也符合题意

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{
    if(root==NULL)
        return false;
    if(issame(root,subRoot))
        return true;
    return isSubtree(root->left,subRoot)
    ||isSubtree(root->right,subRoot);
}
对称二叉树

其实判断二叉树是否对称就是左边和右边比较,对折重合

即:

左子树和右子树相同,左子树的左子树后右子树的右子树相同

我们直接调用上一题的判断树是否相同的函数

然后拿左子树和右子树比较即可

当左子树的根节点和右子树的根节点不相等时只返回false

bool issame(struct TreeNode* rootleft,struct TreeNode* rootright)
{
    if(rootleft==NULL&&rootright==NULL)
        return true;
    if(rootleft==NULL||rootright==NULL)
        return false;
    if(rootleft->val==rootright->val)
    {
        if(issame(rootleft->left,rootright->right)
        &&issame(rootleft->right,rootright->left))
            return true;
    }
    return false;
}
bool isSymmetric(struct TreeNode* root) 
{
    if(root->left==NULL&&root->right==NULL)
        return true;
    if(root->left==NULL||root->right==NULL)
        return false;
    if(root->left->val==root->right->val)
    {
        if(issame(root->left,root->right))
            return true;
    }
    return false;
}
检查两颗树是否相同

这不简简单单,和之前的函数差不多,使用递归就是了

同时为空返回true

有一个为空返回false

两个根节点的值不相等返回false

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);
}
翻转二叉树

反转二叉树就是把左子树变成右子树,右子树变成左子树

很简单,直接先开辟空间存放,然后赋于即可

struct TreeNode* invertTree(struct TreeNode* root) 
{
    if (root == NULL) 
    {
        return NULL;
    }
    struct TreeNode* left = invertTree(root->left);
    struct TreeNode* right = invertTree(root->right);
    root->left = right;
    root->right = left;
    return root;
}
二叉树最大深度

最大深度不就是高度吗,就是层数啊

直接递归,就是左子树和右子树中深度大的那一个+1

int maxDepth(struct TreeNode* root) 
{
    if(root==NULL)
        return 0;
    return fmax(maxDepth(root->left), maxDepth(root->right)) + 1;
}
单值二叉树

单值二叉树就是二叉树所有节点的值都相等

二叉树为空符合题意,返回true

左子树和右子树为空符合题意,只有一个节点,返回true

当有一个不为空时,不为空子树根节点和根节点不相等直接返回false

当两个子树都不为空时判断两个子树的根节点是否相等,不相等直接返回false,然后递归左子树和右子树的根节点

bool isUnivalTree(struct TreeNode* root) 
{
    if(root==NULL)
        return true;
    if(root->left==NULL&&root->right==NULL)
        return true;
    if(root->left==NULL||root->right==NULL)
    {
        if(root->left==NULL)
        {
            if(root->val!=root->right->val)
                return false;
        }
        if(root->right==NULL)
        {
            if(root->val!=root->left->val)
                return false;
        }
    }
    if(root->left!=NULL&&root->right!=NULL)
    {
        if(root->val!=root->left->val||root->val!=root->right->val)
            return false;
    }
    return isUnivalTree(root->left)&&isUnivalTree(root->right);
}

好了,今天的分享到这里就结束了,谢谢大家!

相关文章
|
7月前
|
存储
单链表在线OJ题(详解+图解)
单链表在线OJ题(详解+图解)
51 3
|
7月前
|
存储
单链表在线OJ题二(详解+图解)
单链表在线OJ题二(详解+图解)
34 1
|
7月前
顺序表在线OJ题(详解+图解)
顺序表在线OJ题(详解+图解)
49 1
|
7月前
|
存储 容器
二叉搜索树在线OJ题讲解
二叉搜索树在线OJ题讲解
33 0
|
7月前
|
C++ 容器
『 C++ 』二叉树进阶OJ题(上)
『 C++ 』二叉树进阶OJ题(上)
『 C++ 』二叉树进阶OJ题(上)
|
7月前
二叉树基础OJ题
二叉树基础OJ题
38 1
|
7月前
|
存储 C++ 容器
『 C++ 』二叉树进阶OJ题(下)
『 C++ 』二叉树进阶OJ题(下)
|
7月前
|
C++ 容器
『 C++ 』二叉树进阶OJ题(中)
『 C++ 』二叉树进阶OJ题(中)
|
7月前
|
存储 算法
二叉树进阶OJ题
二叉树进阶OJ题
39 0
|
算法
代码随想录算法训练营第十四天 | LeetCode 102. 二叉树的层序遍历、LeetCode 226. 翻转二叉树、LeetCode 101. 对称二叉树
代码随想录算法训练营第十四天 | LeetCode 102. 二叉树的层序遍历、LeetCode 226. 翻转二叉树、LeetCode 101. 对称二叉树
60 0