首页 > 其他分享 >二叉树基础OJ题

二叉树基础OJ题

时间:2024-08-10 13:56:37浏览次数:16  
标签:right return OJ int 基础 二叉树 NULL root left

前言

二叉树学到现在,我们对递归已经一定程序上的理解了,所有这里为了加深我们对二叉树递归的掌握,我会分享几道基础的练习题来巩固加深我们对二叉树的理解

这里拿出一些二叉树OJ题,我会写出过程详解,如有错误还望指正!题源来自于牛客网和力扣

单值二叉树

这题需要判断每个节点的值是否相同,当根结点的值等于左子树,根结点的值右子树时,左子树等于右子树,那么我们只需要判断于左右节点与根节点的值是否相同就可以了,我们这里的思路是先判断这颗树是否为空,空树也是单值二叉树。如果左右节点的值与它们的根节点不相同,则这棵树不是单值二叉树,返回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);
}

相同的树

如果两棵树都为空,都为空树,则相同返回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);
}

另一棵树的子树

上面我们正好写了判断相同的树的代码,利用上面的代码,判断系统给的树是否是相同的树,左右子树都判断一下,最好可以画一下递归展开图,便于理解

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);
}

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);
}

二叉树的前序遍历

题目要求我们将二叉树前序遍历的结果输出出来并且不能使用递归的方法,我们可以将二叉树前序遍历的结果先放到数组中在将数组输出,先求出二叉树的大小,在动态开辟二叉树大小的空间存放数据,然后前序遍历二叉树就可以了,这里注意在preorder函数中pi需要使用指针,因为形参不改变实参,二叉树的中序遍历和后序遍历只需要改动preorder数组就行了,道理还是和前序遍历一样

int TreeSize(struct TreeNode* root)
{
    return root == NULL ? 0 : 
                TreeSize(root->left) +
                TreeSize(root->right) + 1;
}

void preorder(struct TreeNode* root, int* a, int* pi)
{
    if(root == NULL)
    return;

    a[(*pi)++] = root->val;
    preorder(root->left, a, pi);
    preorder(root->right, a, pi);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    *returnSize = TreeSize(root);
    int* a = (int*)malloc(sizeof(int) * (*returnSize));
    if(NULL == a)
    {
        return NULL;
    }    

    int i = 0;
    preorder(root, a, &i);

    for(i = 0; i < *returnSize; ++i)
    {
        printf("%d ", a[i]);
    }

    return a;
}

二叉树中序遍历

思路与前序遍历一样

int SizeTree(struct TreeNode* root)
{
    return root == NULL ? 0 : SizeTree(root->left) + 
                    SizeTree(root->right) + 1;
}

void inorder(struct TreeNode* root, int* a, int* pi)
{
    if(root == NULL)
    {
        return;
    }

    inorder(root->left, a, pi);
    a[(*pi)++] = root->val; 
    inorder(root->right, a, pi);
}

int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    *returnSize = SizeTree(root);
    int* a = (int*)malloc(sizeof(int) * (*returnSize));
    if(NULL == a)
    {
        return NULL;
    }

    int i = 0;
    inorder(root, a, &i);
    for (i = 0; i < *returnSize; ++i)
    printf("%d ", a[i]);

    return a;
}

二叉树后续遍历

int SizeTree(struct TreeNode* root)
{
    return root == NULL ? 0 : SizeTree(root->left) + 
                    SizeTree(root->right) + 1;
}

void postorder(struct TreeNode* root, int* a, int* pi)
{
    if(root == NULL)
    {
        return;
    }

    postorder(root->left, a, pi);
    postorder(root->right, a, pi);
    a[(*pi)++] = root->val; 
}

int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    *returnSize = SizeTree(root);
    int* a = (int*)malloc(sizeof(int) * (*returnSize));
    if(NULL == a)
    {
        return NULL;
    }

    int i = 0;
    postorder(root, a, &i);
    for (i = 0; i < *returnSize; ++i)
    printf("%d ", a[i]);

    return a;
}

二叉树遍历

我们可以通过题目给的条件以中序遍历的顺序将它的二叉树大致情况画出来,然后将这个二叉树创建出来就可以了,首先创建节点,当我们遍历到#时跳过它拿数组后面的数据,因为在二叉树中它表示的是NULL,所以没有必要存入二叉树,然后以中序遍历的顺序将二叉树的内容打印出来就可以了

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

typedef struct BinaryTree
{
    int val;
    struct BinaryTree* left;
    struct BinaryTree* right;
}BT;

BT* creaTree(char* a, int* pi)
{
    if(a[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }

    BT* node = (BT*)malloc(sizeof(BT));
    node->val = a[(*pi)++];
    node->left = creaTree(a, pi);
    node->right = creaTree(a, pi);
    
    return node;
}

void Print(BT* root)
{
    if(root == NULL)
    {
        return;
    }

    Print(root->left);
    printf("%c ", root->val);
    Print(root->right);

}

int main() {
    char a[100] = {0};
    gets(a);
    int i = 0;
    BT* node = creaTree(a, &i);
    Print(node);
    return 0;
}

对称二叉树

这题我们可以判断该子树的左右子树是否相同,所以我们可以使用相同的树的代码,无非一个判断结构是否相同,一个判断是否对称,只需在递归时将它的左子树与右子树相比较就行了

bool check(struct TreeNode* q, struct TreeNode* p)
{
    if(q == NULL && p == NULL)
    return true;

    if(q == NULL || p == NULL)
    return false;

    if(q->val != p->val)
    return false;

    return check(q->left, p->right) && check(q->right, p->left);
}

bool isSymmetric(struct TreeNode* root) {
    return check(root->left, root->right);
}

平衡二叉树

先算出它左右节点的个数然后在相减,如果小于1就返回false,它的每个左右子树的深度都需要比较

int TreeHeight(struct TreeNode* root)
{
    if(root == NULL)
    {
        return 0;
    }

    int Hleft = TreeHeight(root->left);
    int Hright = TreeHeight(root->right);

    return Hleft > Hright ? Hleft + 1 : Hright + 1; 
}

bool isBalanced(struct TreeNode* root) {
    if(root == NULL)
    return true;

    int left = TreeHeight(root->left);
    int right = TreeHeight(root->right);

    if(abs(left - right) > 1)
    {
        return false;
    }

    return isBalanced(root->left) && isBalanced(root->right);
}

翻转二叉树

我们这里的思路是先翻转子树,然后翻转整个树

struct TreeNode* mirrorTree(struct TreeNode* root){
    if(root == NULL){
        return NULL;
    }

    struct TreeNode *left = mirrorTree(root -> left);
    struct TreeNode *right = mirrorTree(root -> right);
    root -> left = right;
    root -> right = left;
    return root;
}

方便理解,我这里画了递归展开图

递归展开图:

标签:right,return,OJ,int,基础,二叉树,NULL,root,left
From: https://blog.csdn.net/m0_73634434/article/details/140965257

相关文章

  • 零基础转行网络安全真的好就业吗?(非常详细)零基础入门到精通,收藏这一篇就够了
    网络安全作为近两年兴起的热门行业,成了很多就业无门但是想转行的人心中比较向往但是又心存疑惑的行业,毕竟网络安全的发展史比较短,而国内目前网安的环境和市场情况还不算为大众所知晓,所以到底零基础转行入门网络安全之后,好不好就业呢?今天我们就来全面彻底分析一下网络安全对......
  • 【数据结构与算法】输出二叉树中从每个叶子结点到根结点的路径 C++实现(二叉树+栈+深度
    二叉树叶子节点到根节点的路径题目描述给定一棵二叉树的后序遍历序列post[s1..t1]和中序遍历序列in[s2..t2],设计一个算法,输出二叉树中从每个叶子节点到根节点的路径。请使用栈的数据结构解决。输入格式输入包括两行:第一行为后序遍历序列post[s1..t1]。第二行为中序......
  • JDBC数据库连接技术基础及核心API
    目录JDBC的概念JDBC的搭建步骤JDBC的代码实现步骤框架代码实现核心API注册驱动(jdk6.0后可自动注册,无需编写代码)Connection(连接数据库)Statement(用于执行SQL语句,会被SQL注入攻击,后被PreparedStatement替代)PreparedStatement(可以防止SQL注入,全面替代Statement)ResultS......
  • 二叉树的学习
    目录树形结构树中的概念树的表示方法二叉树二叉树的重要性质二叉树的存储遍历中序遍历后续遍历层序遍历创建二叉树二叉树的遍历获取树中节点个数获取叶子节点的个数获取第k层节点个数获取二叉树的高度检测val元素是否存在二叉树相关题目检查两棵树是否相......
  • 【MATLAB源码】数学建模基础教程(2)--层次分析法(评价类算法)
    系列文章目录在最后面,各位同仁感兴趣可以看看!层次分析法引言一、层次分析法的特点二、模型的建立求解过程(1)问题的提出:实际问题的转化(2)建立层次结构模型(3)构造判断(成对比较)矩阵(4)一致性检验:三、层次分析法的优点与局限代码开源最后:总结系列文章目录引言层次分析......
  • 多元时间序列分析统计学基础:基本概念、VMA、VAR和VARMA
    多元时间序列是一个在大学课程中经常未被提及的话题。但是现实世界的数据通常具有多个维度,所以需要多元时间序列分析技术。在这文章我们将通过可视化和Python实现来学习多元时间序列概念。这里假设读者已经了解单变量时间序列分析。1、什么是多元时间序列?顾名思义,多元时间序列是......
  • 二叉树——6.平衡二叉树
    力扣题目链接给定一个二叉树,判断它是否是高度平衡的二叉树。示例:TureFalse首先做这道题目前要明白什么是平衡二叉树?平衡二叉树的定义是,对于二叉树的每一个节点,它的左子树和右子树的高度差不超过1。结合示例中的两个例子理解平衡二叉树的定义。完整代码如下:#Definition......
  • 问题 E: 数据结构基础5-车厢调度
    题目描述有一个火车站,铁路如图所示,每辆火车从A驶入,再从B方向驶出,同时它的车厢可以重新组合。假设从A方向驶来的火车有n节(n<=1000),分别按照顺序编号为1,2,3,…,n。假定在进入车站前,每节车厢之间都不是连着的,并且它们可以自行移动到B处的铁轨上。另外假定车站C可以停放任意多节车厢。......
  • UOJ354 新年的投票
    最近我博客似乎出了点bug,倒是不太会修,将就着看吧。本文主要关注第四个子任务,前面三个有叙述不清的敬请谅解。UOJ354新年的投票Sub1不管人的编号直接爆搜就能够找到一个合法方案。Sub3第\(i\)个人假设自己是第一个\(1\),\(1\simi-1\)的都不能是\(1\),如果自己确实有这......
  • 直播平台开发,基础搜索方式之拼音搜索
    直播平台开发,基础搜索方式之拼音搜索核心思想:先获取的汉字的拼音,然后对其进行匹配获取汉字的拼音我这里使用的是pinyin;简单介说一下pinyin包的用法importpyfrom"pinyin";py("中心");//[['zhōng'],['xīn']]默认是带声调的py("中心",{heteronym:t......