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


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

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

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

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

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


这一篇博客我们继续来看看二叉树的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() 
{//输入字符串//题目给出字符串长度不超过100char 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


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

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


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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

本地Docker部署ZFile网盘打造个人云存储,告别公共网盘让你数据安全感爆棚

文章目录 前言1.关于ZFile2.本地部署ZFile3.ZFile本地访问测试4.ZFile的配置5.cpolar内网穿透工具安装6.创建远程连接公网地址7.固定ZFile公网地址 前言 本文主要介绍如何在Linux Ubuntu系统使用Docker本地部署ZFile文件管理系统&#xff0c;并结合cpolar内网穿透工具实现远程…

职场逆袭!学会管理上司,你也能成为职场赢家

书友们&#xff0c;不要错过了&#xff01;我挖到了一本真正让我彻夜难眠的小说&#xff0c;情节跌宕起伏&#xff0c;角色鲜活得就像从书里跳出来陪你聊天。每一页都是新的惊喜&#xff0c;绝对让你欲罢不能。要是你也在寻找那种让人上瘾的阅读体验&#xff0c;这本书就是你的…

LangChain Ollama实战文献检索助手(三)思维链COT、思维树TOT和思维网NOT

大模型的思考方式有时候并不尽人意。我们可以在提示词中引导大模型如何拆分任务&#xff0c;按部就班地思考。 一、思维链 思维链是引导模型一步一步地思考&#xff0c;分为Zero-Shot CoT和Few-Shot CoT。Zero-Shot CoT就是著名的Let’s think step by step。Few-Shot CoT是对…

ASP页面改为UTF-8编码后,刷新页面不定时中文输出乱码终极解决方案

IIS7下的ASP页面&#xff0c;改为Utf-8编码后&#xff0c;Html部分的中文显示正常&#xff0c;但是由 Response.Write 输出的中文字符&#xff0c;在不特定的时间会变成乱码&#xff0c;一开始以为是浏览器问题&#xff0c;测试了多个浏览器故障依旧不定时出现&#xff1a; &l…

Spring底层源码(一)

Spring的入门代码&#xff1a; public class XmlTest {public static void main(String[] args) {//构造一个容器.ClassPathXmlApplicationContext context new ClassPathXmlApplicationContext("springTest.xml");//从容器中获取Bean对象UserService userService …

理解Web登录机制:会话管理与跟踪技术解析(二)-JWT令牌

JWT令牌是一种用于安全地在各方之间传递信息的开放标准&#xff0c;它不仅能够验证用户的身份&#xff0c;还可以安全地传递有用的信息。由于其结构简单且基于JSON&#xff0c;JWT可以在不同的系统、平台和语言间无缝传递&#xff0c;成为现代Web开发中不可或缺的一部分。 文章…

SpringBoot源码解析(二):引导上下文DefaultBootstrapContext

SpringBoot源码系列文章 SpringBoot源码解析(一)&#xff1a;SpringApplication构造方法 SpringBoot源码解析(二)&#xff1a;引导上下文DefaultBootstrapContext 目录 前言一、入口二、DefaultBootstrapContext1、BootstrapRegistry接口2、BootstrapContext接口3、DefaultBo…

运维高可用架构设计

一、硬件 1、服务器 2、网络架构 二、软件 1、基础组件 组件名称 高可用方式 最少节点数 负载均衡(Tenginx) corsyncpacemaker互为主备 多组集群通过DNS轮循实现一个大集群 2DNS主从集群2RabbitMQ原生HA镜像集群3Zookeeper原生分布式集群3Kafka原生分布式集群3ES原生分布式集…

C++之vector类的模拟实现

片头 嗨~小伙伴们&#xff0c;今天我们来一起学习关于C的vector类的模拟实现&#xff0c;准备好了吗&#xff1f;咱们开始咯~ 一、基本框架 namespace bit {template<class T>class vector {public:typedef T* iterator;typedef const T* const_iterator;// 针对const修…

MyBatis 返回 Map 或 List<Map>时,时间类型数据,默认为LocalDateTime,响应给前端默认含有‘T‘字符

一、问题 MyBatis 返回 Map 或 List时&#xff0c;时间类型数据&#xff0c;默认为LocalDateTime Springboot 响应给前端的LocalDateTime&#xff0c;默认含有’T’字符&#xff0c;如何统一配置去掉 二、解决方案 1、pom.xml 增加依赖&#xff08;2024.11.6 补充&#xff…

数据结构之二叉树前序,中序,后序习题分析(递归图)

1.比较相同的树 二叉树不能轻易用断言&#xff0c;因为树一定有空 2.找结点值 3.单值二叉树 4.对称二叉树 5.前序遍历

如何使用gewe开发微信机器人

[Gewe](微信管理系统)&#xff0c;个人微信**开源框架&#xff0c;支持二次开发、任意语言都可接入&#xff0c;Restful API接入。 gewe框架优势&#xff1a; - 简单易用&#xff0c;无接入难度&#xff0c;区别于其它开源项目&#xff0c;本框架无需用户安装电脑微信&#x…

vue3 基于element-plus进行的一个可拖动改变导航与内容区域大小的简单方法

1、先上个截图&#xff1a; 说明&#xff1a;拖动上面的分隔栏就可以实现&#xff0c;改变左右区域的大小。 2、上面的例子来自官网的&#xff1a; Container 布局容器 | Element Plus 3、拖动的效果来自&#xff1a; https://juejin.cn/post/7029640316999172104#heading-1…

Excel 无法打开文件

Excel 无法打开文件 ‘新建 Microsoft Excel 工作表.xlsx",因为 文件格式或文件扩展名无效。请确定文件未损坏&#xff0c;并且文件扩展名与文件的格式匹配。

K8S node节点没有相应的pod镜像运行故障处理办法

查看从节点状态 kubectl describe node k8s-node1以下是报错提示 解决办法 需要处理node1节点上的磁盘空间&#xff0c;磁盘空间需要在85%内 处理后的状态 处理正常

使用代理时Stable Diffusion无法正常下载各类模型的解决办法

最近发现了 Stable Diffusion 这个好玩的ai绘画工具&#xff0c;不得不感叹现在ai工具已经进化到这么简单易用的程度&#xff0c;只要下载对应的模型就可以生成各种有意思的图片 就算你没有编程基础&#xff0c;跟着教程也能弄出来 不过使用过程中发现部分功能无法使用 查看日…

GODOT 4 不用scons编译cpp扩展的方法

以terrain3d插件&#xff0c;Godot_v4.3 为例&#xff1a; 下载下来&#xff0c;先用scons编译一遍通过后&#xff0c;整个占用1GB&#xff0c;obj文件都生成在源码旁边&#xff0c;够乱。 scons 是跨平台的构建工具&#xff0c;但是需要需要写python脚本。流程比较莫名其妙…

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

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

基于Java的简单图书管理系统的实现(增删改查)

基于Java的简单图书管理系统的实现&#xff08;增删改查&#xff09; package com.situ.lib;public class Book {//对象&#xff1a;书-----定义书的属性:private String name;private String isbn;private String author;private double price;//无参构造方法&#xff1a;pub…

C语言必做30道练习题

C语言练习30题&#xff08;分支循环&#xff0c;数组&#xff0c;函数&#xff0c;递归&#xff0c;操作符&#xff09; 目录 分支循环1.闰年的判断2.阅读代码&#xff0c;计算代码输出的结果3.输入一个1~7的数字&#xff0c;打印对应的星期几4.输入任意一个整数值&#xff0c;…