【数据结构与算法】:二叉树经典OJ

目录

  • 1. 二叉树的前序遍历 (中,后序类似)
  • 2. 二叉树的最大深度
  • 3. 平衡二叉树
  • 4. 二叉树遍历

1. 二叉树的前序遍历 (中,后序类似)

在这里插入图片描述

这道题的意思是对二叉树进行前序遍历,把每个结点的值都存入一个数组中,并且返回这个数组。

思路:
这题与我们平时写的二叉树前序遍历不同。需要我们自己开辟空间,但又由于二叉树结点个数未知,所以在开辟空间之前要先计算结点个数,根据结点个数开辟空间。最后再利用分治递归进行前序遍历。

代码实现如下:

注意:
(1) 结点个数的计算,数组空间的开辟;
(2) 递归时一般用子函数 _prevOrder 递归,而不是 preorderTraversal 原函数,不然会重复的开辟空间;

(3) 局部变量 i 一定要传地址,因为每一层递归函数都有一个 i ,下一层放的 i 是 i++之后的 i ,由于形参是实参的一份临时拷贝,若不传地址,就不会影响上一层函数中的 i ,就是加的不是同一个 i ;

(4) 输出型参数 returnSize ,目的是获取a数组有多大。


//前序遍历
void _prevOrder(struct TreeNode* root, int* a, int* pi)
{if (root == NULL)return;a[*pi] = root->val;(*pi)++;_prevOrder(root->left, a, pi);_prevOrder(root->right, a, pi);
}//由于不知道数组开多大的空间,所以要提前计算树的结点个数
int TreeSize(struct TreeNode* root)
{return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}int* preorderTraversal(struct TreeNode* root, int* returnSize) {int size = TreeSize(root);//开辟数组空间int* a = (int*)malloc(sizeof(int) * size);int i = 0;_prevOrder(root, a, &i);*returnSize = size;return a;
}

2. 二叉树的最大深度

在这里插入图片描述

思路:
利用分治递归思想。若根节点为空,则深度为0;若非空,则先求左右子树的深度,我的深度 = 左右子树深度大的 + 1。

代码实现如下:

注意:
要先用两个变量记录计算好的左右子树的深度!不然运行时会超出时间限制。


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

3. 平衡二叉树

在这里插入图片描述

平衡二叉树:是指该树所有节点的左右子树的深度相差不超过 1。

思路:
首先计算出每个节点的左右子树的深度,再计算它们的深度差是否超过1。

代码实现如下:


int maxDepth(struct TreeNode* root) {if (root == NULL){return 0;}int leftDepth = maxDepth(root->left);int rightDepth = maxDepth(root->right);return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}bool isBalanced(struct TreeNode* root) {if (root == NULL)return true;int leftDepth = maxDepth(root->left);int rightDepth = maxDepth(root->right);//先检查自己满不满足,再递归检查左子树,右子树满不满足return abs(leftDepth - rightDepth) < 2&& isBalanced(root->left)&& isBalanced(root->right);
}

4. 二叉树遍历

在这里插入图片描述

思路:
首先要根据输入的字符串构建一棵二叉树,再进行中序遍历。

代码实现如下:

注意:
局部变量 i 要传地址,不然递归调用时加的不是同一个 i。


//定义结点
typedef struct TreeNode
{struct TreeNode* left;struct TreeNode* right;char val;
}TNode;//创建二叉树
TNode* CreateTree(char* a, int* pi)
{if (a[*pi] == '#'){(*pi)++;return NULL;}TNode* root = (TNode*)malloc(sizeof(TNode));if (root == NULL){perror("malloc fail!\n");exit(-1);}root->val = a[*pi];(*pi)++;root->left = CreateTree(a, pi);root->right = CreateTree(a, pi);return root;
}void InOrder(TNode* root)
{if (root == NULL)return;InOrder(root->left);printf("%c ", root->val);InOrder(root->right);
}int main() {char str[100] = { 0 };scanf("%s", str);int i = 0;//构建一棵树TNode* root = CreateTree(str, &i);InOrder(root);return 0;
}

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

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

相关文章

解决 IDEA每次打开新的项目都要重新设置maven问题

目录 一、当前项目设置maven 如下图&#xff1a; 二、设置打开的新项目的maven 如下图&#xff1a;​ 一、当前项目设置maven 对于当前项目我们都知道设置maven的配置要在 File -- Settings -- Build -- Maven 中设置 如下图&#xff1a; 二、设置打开的新项目的maven F…

150个 HTML5 网站模版 量大慢选

HTML5 网站模版 No.1 HTML5 网站模版 No.1

linux下安装nacos2.2.0

1、获取下载地址并下载 1.1、打开nacos官网 1.2、找到对应版本&#xff0c;点进去 ## 1.3、复制地址 1.4下载 # 进入要安装的目录&#xff0c;cd /usr/local/src # 执行wget https://github.com/alibaba/nacos/releases/download/2.2.0/nacos-server-2.2.0.tar.gz2、 安装…

RTSP/Onvif安防视频EasyNVR平台 vs.多协议接入视频汇聚EasyCVR平台:设备分组的区别

EasyNVR安防视频云平台是旭帆科技TSINGSEE青犀旗下支持RTSP/Onvif协议接入的安防监控流媒体视频云平台。平台具备视频实时监控直播、云端录像、云存储、录像检索与回看、告警等视频能力&#xff0c;能对接入的视频流进行处理与多端分发&#xff0c;包括RTSP、RTMP、HTTP-FLV、W…

架构设计参考项目系列主题:新零售SaaS架构:客户管理系统架构设计

什么是客户管理系统? 客户管理系统,也称为CRM(Customer Relationship Management),主要目标是建立、发展和维护好客户关系。 CRM系统围绕客户全生命周期的管理,吸引和留存客户,实现缩短销售周期、降低销售成本、增加销售收入的目的,从而提高企业的盈利能力和竞争力。 …

【ARM 裸机】汇编 led 驱动之原理分析

1、我们为什么要学习汇编&#xff1f;&#xff1f;&#xff1f; 之前我们或许接触过 STM32 以及其他的 32 位的 MCU ,都是基于 C 语言环境进行编程的&#xff0c;都没怎么注意汇编&#xff0c;是因为 ST 公司早已将启动文件写好了&#xff0c;新建一个 STM32 工程的时候&#…

nexus搭建maven与docker镜像的私有仓库

引言 通过nexus搭建maven与docker镜像的私有仓库,实现jar包与镜像动态更新、共享、存储。 一、nexus部署 通过docker-compose部署nexus name: java services:#############################环境#############################env-nexus:restart: always## 3.58.1image: so…

Python十大最佳实践:高效Python编程的十个关键方法

在当今的软件开发世界中&#xff0c;Python是一种极其重要且广泛使用的编程语言。以下是Python编程的十大最佳实践&#xff0c;这些实践将帮助你提升编程效率&#xff0c;优化代码质量&#xff0c;以及更好地应用Python的强大功能。 1.理解Pythonic的方式 “Pythonic”是指遵循…

普乐蛙VR航天体验馆设备VR太空飞船VR元宇宙展厅

三天小长假就要来啦&#xff01;五一假期也即将到来。老板们想捉住人流量这个财富密码吗&#xff1f;那快快行动起来&#xff01;开启VR体验项目&#xff0c;假期赚翻天&#xff01;小编亲测&#xff01;&#xff01;这款设备刺激好玩&#xff0c;想必会吸引各位家长小孩、学生…

matlab使用教程(43)—二维曲线图绘制的基本方法

这个博客创建一个简单的曲线图并修改横纵坐标。通过更改线条颜色、线型和添加标记来自定义线图的外观。 1.创建曲线图 使用 plot 函数创建二维曲线图。例如&#xff0c;绘制从 0 到 2 π 之间的正弦函数值&#xff0c;并修改横纵坐标&#xff0c;添加图形标题。 x linspace…

ES6 关于Class类的继承 extends(2024-04-10)

1、简介 类Class 可以通过extends关键字实现继承&#xff0c;让子类继承父类的属性和方法。extends 的写法比 ES5 的原型链继承&#xff0c;要清晰和方便很多。 class Foo {constructor(x, y) {this.x x;this.y y;console.log(父类构造函数)}toString() {return ( this.x …

【算法】分治-快排

个人主页 &#xff1a; zxctscl 如有转载请先通知 题目 前言1. 75. 颜色分类1.1 分析1.2 代码 2. 912. 排序数组2.1 分析2.2 代码 3. 215. 数组中的第K个最大元素3.1 分析3.2 代码 4. LCR 159. 库存管理 III4.1 分析4.2 代码 前言 分治就是分而治之 1. 75. 颜色分类 1.1 分析…

GitHub repository - Pulse - Contributors - Network

GitHub repository - Pulse - Contributors - Network 1. Pulse2. Contributors3. NetworkReferences 1. Pulse 显示该仓库最近的活动信息。该仓库中的软件是无人问津&#xff0c;还是在火热地开发之中&#xff0c;从这里可以一目了然。 2. Contributors 显示对该仓库进行过…

设备树的概念、设备树如何变成device、与driver的匹配

在平台总线驱动模型中资源和驱动已经从逻辑上和代码组织上进行了分离&#xff0c;但每次调整资源还是会涉及到内核&#xff0c;所以现在更加流行的是设备树方式。设备树的好处是通过独立于内核存在&#xff0c;这样如果设备上外设功能启用与否以及位置变动的话很多时候不用修改…

深入理解计算机网络分层结构

一、 为什么要分层&#xff1f; 计算机网络分层的主要目的是将复杂的网络通信过程分解为多个相互独立的层次&#xff0c;每个层次负责特定的功能。这样做有以下几个好处&#xff1a; 模块化设计&#xff1a;每个层次都有清晰定义的功能和接口&#xff0c;使得网络系统更易于设…

修复 Windows 上的 PyTorch 1.1 github 模型加载权限错误

问题: 在 Windows 计算机上执行示例 github 模型加载时,生成了 master.zip 文件的权限错误(请参阅下面的错误堆栈跟踪)。 错误堆栈跟踪: 在[4]中:en2de = torch.hub.load(pytorch/fairseq, transformer.wmt16.en-de, tokenizer=moses, bpe=subword_nmt) 下载:“https://…

【Java基础题型】矩阵的对角线求和

一、题目-矩阵 求一个33矩阵对角线元素之和。 输入格式 矩阵 输出格式 主对角线 副对角线 元素和 样例输入 1 2 3 1 1 1 3 2 1 样例输出 3 7 二、参考的知识 这里给大家送点英语单词&#xff0c;记得学习&#xff1a; p r i m a r y. adj.主要的&#xff1b;初…

谈谈我的软考高级考证之路(系统架构设计师篇)

系统架构设计师备考资料请移步 2023年软考高级系统架构设计师视频教程&#xff0c;推荐下载&#xff01;获取。 备考总体策略 • 总体策略&#xff1a;刷视频记笔记刷真题 • 备考时间&#xff1a;建议报完名之后&#xff0c;开始备考&#xff0c;大致2-3个月&#xff08;基础…

CNN-Transformer时间序列预测

部分代码&#xff1a; # CNN-Transformer class CNNTransformerEncoder(nn.Module):def __init__(self, input_features, transformer_encoder_heads,embedding_features, cnn_kernel_size, dim_feedforward_enc, n_encoder_layer):super(CNNTransformerEncoder, self).__init…

复旦新出!大规模语言模型:从理论到实践,书籍PDF分享

自2018年以来&#xff0c;包含Google、OpenAI、Meta、百度、华为等公司和研究机构都纷纷发布了包括BERT&#xff0c; GPT等在内多种模型&#xff0c;并在几乎所有自然语言处理任务中都表现出色。 今天给大家推荐一本大模型方面的书籍<大规模语言模型&#xff1a;从理论到实…