题目练习之二叉树那些事儿(续集)


♥♥♥~~~~~~欢迎光临知星小度博客空间~~~~~~♥♥♥

♥♥♥零星地变得优秀~也能拼凑出星河~♥♥♥

♥♥♥我们一起努力成为更好的自己~♥♥♥

♥♥♥如果这一篇博客对你有帮助~别忘了点赞分享哦~♥♥♥

♥♥♥如果有什么问题可以评论区留言或者私信我哦~♥♥♥


这一篇博客我们继续来看看二叉树的OJ题目练习~

练习1:二叉树的前序遍历

力扣——144二叉树的前序遍历

题目

二叉树的遍历前面我们说过有四种遍历方式,这里需要我们进行前序遍历,我们可以看到它输出结果是没有NULL的,所以为空时直接返回就好了。同时我们可以看到函数第二个参数是int* 类型的,根据他的名字returnSize我们猜测它是前序遍历到的结点个数~并且函数返回类型也是int* ,说明我们需要返回前序遍历结果的数组~

思路

知道了题目的要求,我们可以有下面的思路

首先求出二叉树的结点个数,创建一个结点个数大小的数组,前序遍历将结点保存的数据放到数组中,返回数组

代码

//重定义
typedef struct TreeNode TreeNode;

//总结点个数=1+左子树结点个数+右子树结点个数
int BinarySize(TreeNode* root)
{
    if(root == NULL)
    {
        return 0;
    }
    return 1 + BinarySize(root->left) + BinarySize(root->right);
}
void PreOrder(TreeNode* root,int* arr,int* pi)
{
    if(root == NULL)
    {
        return;
    }
    //前序遍历
    //根左右
    arr[(*pi)++] = root->val;
    PreOrder(root->left, arr, pi);
    PreOrder(root->right, arr, pi);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    //求二叉树结点个数
    *returnSize = BinarySize(root);
    //申请空间
    int* arr = (int*)malloc((*returnSize) * sizeof(int));
    //前序遍历,保存数据到数组中
    int i = 0;
    //数组下标从0开始
    PreOrder(root,arr,&i);
    //返回数组
    return arr;
}

提交成功~

接下来两个题目是与这个题类似的,思路代码都是类似的~我们这里就直接给出代码~

练习2:二叉树的中序遍历

力扣——94二叉树的中序遍历

 //重定义
typedef struct TreeNode TreeNode;

//总结点个数=1+左子树结点个数+右子树结点个数
int BinarySize(TreeNode* root)
{
    if (root == NULL)
    {
        return 0;
    }
    return 1 + BinarySize(root->left) + BinarySize(root->right);
}

void InOrder(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 = BinarySize(root);
    //申请空间
    int* arr = (int*)malloc((*returnSize) * sizeof(int));
    //中序遍历,保存数据到数组中
    int i = 0;
    //数组下标从0开始
    InOrder(root, arr, &i);
    //返回数组
    return arr;
}

练习3:二叉树的后序遍历

力扣——145二叉树的后序遍历

//重定义
typedef struct TreeNode TreeNode;

//总结点个数=1+左子树结点个数+右子树结点个数
int BinarySize(TreeNode* root)
{
    if (root == NULL)
    {
        return 0;
    }
    return 1 + BinarySize(root->left) + BinarySize(root->right);
}

void PostOrder(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 = BinarySize(root);
    //申请空间
    int* arr = (int*)malloc((*returnSize) * sizeof(int));
    //后序遍历,保存数据到数组中
    int i = 0;
    //数组下标从0开始
    PostOrder(root, arr, &i);
    //返回数组
    return arr;
}

提交通过~

练习4:二叉树遍历

牛客——二叉树遍历

题目

这里我们会发现题目希望我们编写一个程序,而不是一个函数,那么这里就需要我们自己去创建二叉树,定义二叉树结点,不能使用现成的。

看看题目:题目希望我们给一个给定的字符串进行构造一个二叉树(#代表空格,同时也代表着空树),并且中序遍历二叉树,输出中序遍历二叉树的结果~

思路

首先我们需要定义二叉树结点,申请结点根据给定的字符串构造二叉树(这里我们构造二叉树采用的也是递归构造的方法,先构造根结点,再构造左右子树)最后进行中序遍历输出结果

代码

#include <stdio.h>
#include <stdlib.h>//malloc头文件

//定义二叉树结点
typedef char BTNodeDataTye;
typedef struct BinaryTreeNode
{
    BTNodeDataTye data;
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
}BTreeNode;

BTreeNode* BuyNode(BTNodeDataTye x)
{
    BTreeNode* newnode = (BTreeNode*)malloc(sizeof(BTreeNode));
    if(newnode == NULL)
    {
        perror("malloc fail");
        exit(1);
    }
    newnode->data = x;
    newnode->left = newnode->right = NULL;
    return newnode;
}
BTreeNode* BTreeCreate(BTNodeDataTye* arr,int* pi)
{
    //取到字符串下标为(*pi)的数据创建结点
    if(arr[*pi] == '#')
    {
        //往后面走,这里为空结点
        ++(*pi);
        return NULL;
    }
    BTreeNode* root = BuyNode(arr[*pi]);
    //字符串下标往后面走
    ++(*pi);
    //递归构造左右子树
    root->left = BTreeCreate(arr,pi);
    root->right = BTreeCreate(arr,pi);
    return root;
}

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

int main() 
{
    //输入字符串//题目给出字符串长度不超过100
    char arr[100];
    scanf("%s",arr);
    //构造二叉树
    int i = 0;
    //i传地址,形参改变才会影响实参
    BTreeNode* root = BTreeCreate( arr, &i);
    //中序遍历
    Inorder(root);
    return 0;
}

提交通过~我们再一次体会了递归的暴力美学~

除此之外,我的博客即将同步至腾讯云开发者社区,邀请大家一同入驻:https:/cloud.tencent.com/developer/support-plan?invite_code=34m59s418000k


♥♥♥本篇博客内容结束,期待与各位优秀程序员交流,有什么问题请私信♥♥♥

♥♥♥如果这一篇博客对你有帮助~别忘了点赞分享哦~♥♥♥


本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/910531.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

删除MacOS下PowerPoint烦人的加载项

起因 最近要写论文&#xff0c;需要插入很多公式&#xff0c;利用自带的吧&#xff0c;太过繁琐&#xff0c;每次插入都需要点击插入-公式-符号&#xff0c;然后头脑发热想用下本科写论文时用过的MathType&#xff0c;结果这货现在要收费了&#xff0c;新版本只能适用30天&…

清华双臂机器人扩散大模型RDT:先预训练后微调,支持语言、图像、动作多种输入(1B参数)

前言 通过上文介绍的GR2&#xff0c;我们看到了视频生成模型在机器人训练中的应用 无独有偶&#xff0c;和GR2差不多一个时期出来的清华RDT&#xff0c;其模型架构便基于视频生成架构DiT改造而成(当然&#xff0c;该清华团队其实也在DiT之前推出了U-ViT&#xff0c;具体下文会…

Linux下GCC编译器的安装

Linux下GCC编译器的安装 以下所有的版本都可以在https://gcc.gnu.org/pub/gcc/infrastructure/这里找最新的 通过apt-get方式下载的Qt5.9的gcc编译器版本只是4.8.3&#xff0c;无法打开一些Qt5的库头文件&#xff0c;所以准备在Llinux下再安装一个gcc5.3.0。 查看gcc版本 ubu…

qt相关知识

lineEdit中的一些知识 首先我要设置lineEdit中的文本怎么操作 ui->lineEdit->setText(); 如何给窗口设置名字 this->setWindowTitle("计算器"); 如何给按钮设置我们的图片 QIcon ic("图片地址")&#xff1b; ui->button->setIcon(ic…

使用官网tar包制作OpenSSL及OpenSSH rpm包进行升级安装(OpenSSH_9.9p1, without OpenSSL未解决)

一、制作openssl-1.1.1w.rpm包 1、安装基础依赖包和rpmbuild及其依赖包 yum install curl which make gcc perl perl-WWW-Curl rpm-build rpm-build rpmdevtools tree -y yum install gcc-c glibc glibc-devel openssl openssl-devel \pcre-devel zlib zlib-devel perl…

WAL日志

1.WAL概述 PG WAL&#xff08;Write-Ahead Logging&#xff09;日志是PostgreSQL数据库中的一种重要机制&#xff0c;用于保证数据库的完整性和数据恢复。 1.1定义与功能 WAL日志是PostgreSQL的持久性技术&#xff0c;它将所有对数据库的修改操作&#xff08;如INSERT、UPDA…

开放寻址法、链式哈希数据结构详细解读

一、开放寻址法&#xff08;Open Addressing&#xff09; 1. 定义 开放寻址法是一种哈希冲突解决策略&#xff0c;所有元素都存储在哈希表中。当发生冲突时&#xff0c;即两个键计算出的哈希值相同时&#xff0c;会按照一定的探查序列查找下一个可用的位置来存储新元素。 2.…

算法通关(4)-- 前缀树

前缀数原理和代码 原理 前缀树&#xff08;Trie树&#xff09;&#xff0c;也称为字典树&#xff0c;是一种用于高效存储和检索字符串的数据结构。它是一种树形结构&#xff0c;能够利用字符串的公共前缀来减少存储空间和查询时间。 现在有“acb”,"cba","ac…

CSS3新增渐变(线性渐变、径向渐变、重复渐变)

1.线性渐变 代码&#xff1a; 效果图&#xff1a; 使文字填充背景颜色&#xff1a; 效果图&#xff1a; 2.径向渐变 代码&#xff1a; 效果图&#xff1a; 代码图&#xff1a; 效果图&#xff1a; 3.重复渐变 代码&#xff1a; 效果图&#xff1a;

Python 学习完基础语法知识后,如何进一步提高?

入门Python后&#xff0c;就可以拿些小案例练手了&#xff0c;这时候千万不要傻乎乎地成天啃语法书。 编程是一门实践的手艺&#xff0c;讲究孰能生巧。不管是去手撸算法、或者照葫芦画瓢写几个小游戏都可以让你的Python突飞猛进。 之前看github比较多&#xff0c;推荐给大家…

blender导入的图片渲染看不见,图片预览正常,但渲染不出

在使用Blender时&#xff0c;我们经常会遇到导入图片后在预览渲染中显示&#xff0c;但在实际渲染时图片消失的问题。本文将提供详细的解决方法&#xff0c;帮助大家解决“Blender导入的图片渲染图像不显示”的问题。 问题原因 导入的图片在Blender中只是一张图&#xff0c;并…

【数据结构】选择排序——选择排序 和 堆排序

选择排序 和 堆排序 一、选择排序选择排序的思路及其代码选择排序的弊端 二、堆排序三、速度对比同时排10000个数同时排100000个数同时拍500000个数堆排 1 亿个数 一、选择排序 选择排序的思路及其代码 选择排序思路很简单 就是经过将数组遍历选择最小值 将最小值位置的数与数…

Docker在CentOS上的安装与配置

前言 随着云计算和微服务架构的兴起&#xff0c;Docker作为一种轻量级的容器技术&#xff0c;已经成为现代软件开发和运维中的重要工具。本文旨在为初学者提供一份详尽的指南&#xff0c;帮助他们在CentOS系统上安装和配置Docker及相关组件&#xff0c;如Docker Compose和私有…

大数据新视界 -- 大数据大厂之 Impala 性能优化:数据存储分区的艺术与实践(下)(2/30)

&#x1f496;&#x1f496;&#x1f496;亲爱的朋友们&#xff0c;热烈欢迎你们来到 青云交的博客&#xff01;能与你们在此邂逅&#xff0c;我满心欢喜&#xff0c;深感无比荣幸。在这个瞬息万变的时代&#xff0c;我们每个人都在苦苦追寻一处能让心灵安然栖息的港湾。而 我的…

CLIP论文CLIP 改进工作串讲

文章目录 CLIPViLTCLIP 改进工作串讲Lseg&#xff08;Language -driven semantic segmentation)Group ViT&#xff08;Semantic Segmentation Emerges from Text Supervision&#xff09;ViLDGLIP_V1/V2&#xff08;Ground Language-Image Pre-train&#xff09;CLIP PassoCLIP…

C++:set详解

文章目录 前言一、set概念介绍二、set的使用1. 插入删除相关2. 查找相关1&#xff09;find2&#xff09;count3&#xff09;lower_bound与upper_bound4&#xff09;equal_range 三、set的值是不能修改的原理四、基于哈希表的set总结 前言 根据应用场景的不同&#xff0c;STL总…

【静态页面】尚品汇 1、设计稿分析及资源准备

目录 1. 准备工作2. 理解设计3. 规划项目结构 1. 准备工作 安装必要的工具&#xff1a;确保你的开发环境已经准备好&#xff0c;包括文本编辑器&#xff08;如 VSCode&#xff09;、浏览器等。获取设计文件&#xff1a;获取UI设计稿或者设计文件链接&#xff0c;并确保可以访问…

小时收入:衡量工作效率与个人自由的标准

小时收入&#xff0c;就是按照小时来计算一个人的收入。比如&#xff0c;一个月一共工作200小时&#xff0c;获得的总收入是20000元&#xff0c;那么小时收入就是100元/小时。 小时收入可以反应一个人的赚钱效率。 可能两个人的月收入一样&#xff0c;但是付出的总工作时间不…

RFID文件柜在文件管理中的作用

一、RFID文件柜系统概述 1.1 RFID技术简介 RFID&#xff08;Radio Frequency Identification&#xff0c;无线射频识别&#xff09;技术是一种非接触式的自动识别技术&#xff0c;它通过无线电讯号识别特定目标并读写相关数据&#xff0c;无需识别系统与特定目标之间建立机械…