【数据结构】二叉树运用及相关例题
文章目录
- 前言
- 查第K层的节点个数
- 判断该二叉树是否为完全二叉树
- 例题一 - Leetcode - 226反转二叉树
- 例题一 - Leetcode - 110平衡二叉树
前言
在笔者的前几篇篇博客中介绍了二叉树的基本概念及基本实现方法,有兴趣的朋友自己移步看看。
这篇文章主要介绍一下二叉树的其他的几个重要功能实现方法,并对几道例题进行一个分析和解答
查第K层的节点个数
就比如上图,第一层有1个节点,第二层2个,第三次3个
这个还是比较简单的,我们只需要传进去一个能够证明现在是第几层的变量,然后递归左右节点,为空返回NULL,有值且满足层级要求,返回1,就可以完成了
代码如下
nt TreeLevelKSize(BTNode* root, int k)
{if (root == NULL)return 0;if (k == 1)return 1;// 子问题return TreeLevelKSize(root->left, k - 1)+ TreeLevelKSize(root->right, k - 1);
}
判断该二叉树是否为完全二叉树
首先提一下满二叉树的概念,即
一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是 说,如果一个二叉树的层数为K,且结点总数是2^k-1,则它就是满二叉树。
这里与完全二叉树进行一下区分
完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K 的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
两者的图例如下
回到判断环节,我们需要用到之前说过的一个层序遍历即
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{if (root == NULL) {return;}// 使用队列实现层序遍历int front = 0, rear = 0;BTNode** queue = (BTNode**)malloc(sizeof(BTNode*) * 1000); // 假设节点数不超过1000queue[rear++] = root;while (front < rear) {BTNode* current = queue[front++]; // 取出队列前端节点printf("%c ", current->data);if (current->left != NULL) {queue[rear++] = current->left; // 左子节点入队}if (current->right != NULL) {queue[rear++] = current->right; // 右子节点入队}}free(queue); // 释放队列内存
}
而这里我们需要做的就是下面两部
1、层序遍历走,空也进队列
2、遇到第一个空节点时,开始判断,后面全空就是完全二叉树,后面有非空就不是完全二叉树
比如这个图,我们建立一个队列,不断遍历将左右节点加入到队列中去,而7的位置为空
我们通过循环判断队列是否为空,每次循环出队一个头节点,尾插左右节点,不论是否为空
完成这步后,等遇到的节点为空时,退出循环,开始判断这个队列是否为空(因为我们在添加时,加入了很多新的空值,所以我们需要遍历队列里面的元素,一旦遇到有元素不为空,就代表空节点后还有元素,就比如上图的7后面还有5,6一样。
代码如下
bool TreeComplete(BTNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);// 遇到第一个空,就可以开始判断,如果队列中还有非空,就不是完全二叉树if (front == NULL){break;}QueuePush(&q, front->left);QueuePush(&q, front->right);}while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);// 如果有非空,就不是完全二叉树if (front){QueueDestroy(&q);return false;}}
注意:
- 因为我们之前创建的队列是通过数组建的,而数组的值往往设定为int,这里如果不是二外创建新的数组就像上面层序遍历那样,就记得使用将队列中数组的元素设为二叉树节点的类型
- 另外可能有朋友会认为在添入队列时堆对NULL(空节点)进行引用,将空节点的子节点,实则不会,因为我们是通过循环使左右子节点加入,一次仅加入两个,不会因为循环过快导致上述现象
例题一 - Leetcode - 226反转二叉树
Leetcode - 226反转二叉树
这题的思路没那么复杂,我们抓住他反转的本质,其实就是每个节点的左右节点交换,这样一来就完成了,代码如下
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/typedef struct TreeNode TreeNode;
struct TreeNode* invertTree(struct TreeNode* root) {if(root == NULL)return NULL;TreeNode* left = invertTree(root->left);TreeNode* right = invertTree(root->right);root->left = right;root->right = left;return root;
}
值得一提的是,这里我们不是先进行递归,在对左右节点赋值的吗,因为二叉树的本质还是一种链表,是一种逻辑结构。
所以,即使我们先将左右节点交换再递归下去,是不会影响最终结果的,比如下面这串代码
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
typedef struct TreeNode TreeNode;
struct TreeNode* invertTree(struct TreeNode* root) {if(root == NULL){return NULL;}TreeNode* left = root->left;TreeNode* right = root->right;root->right = left;root->left = right;left = invertTree(root->left);right = invertTree(root->right);return root;
}
例题一 - Leetcode - 110平衡二叉树
Leetcode - 110平衡二叉树
关于这道题我们需要了解一个概念,即平衡二叉树
所以我们可以通过方法名来获取一个节点的深度,对左右两个节点进行比较,若插值不大于1即可
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
#define MAX(a,b) ((a)>(b)?(a):(b))
int height(struct TreeNode* root)
{if(root == NULL)return 0;return MAX(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));
}
于是我们可以按照思路这样写出,但是这个写法存在较大缺陷,就是时间复杂度太高了,由于是自顶向下递归,因此对于同一个节点,函数 height 会被重复调用,导致时间复杂度较高。如果使用自底向上的做法,则对于每个节点,函数 height 只会被调用一次。即
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
#define MAX(a,b) ((a)>(b)?(a):(b))
int height(struct TreeNode* root)
{if(root == NULL)return 0;int leftHeight = height(root->left);int rightHeight = height(root->right);if(leftHeight == -1 || rightHeight == -1 || fabs(leftHeight - rightHeight) > 1){return -1;}else{return MAX(leftHeight, rightHeight) + 1;}
}
bool isBalanced(str
uct TreeNode* root) {return height(root) != -1;}
相关文章:

【数据结构】二叉树运用及相关例题
文章目录 前言查第K层的节点个数判断该二叉树是否为完全二叉树例题一 - Leetcode - 226反转二叉树例题一 - Leetcode - 110平衡二叉树 前言 在笔者的前几篇篇博客中介绍了二叉树的基本概念及基本实现方法,有兴趣的朋友自己移步看看。 这篇文章主要介绍一下二叉树的…...

Java基础知识点(反射、注解、JDBC、TCP/UDP/URL)
文章目录 反射反射的定义class对象反射的操作 注解注解的定义注解的应用注解的分类基准注解元注解 自定义注解自定义规则自定义demo JDBCTCP/UDP/URLTCPUDPURL 反射 反射的定义 Java Reflection是Java被视为动态语言的基础啊, 反射机制允许程序在执行期间接入Refl…...

postgressql——Tuple学习(2)
Tuple含义 作用 PG并没有像Oracle那样的undo来存放旧数据,而且PG没有真正意义上的delete,而是将旧版本直接存放于relation文件中,也就是成为了dead tuple。我们可以理解成“过期的数据”含义 tuple就相当于一个存储数据的小容器,…...
Linux日志管理
文章目录 一、日志管理概述1.1、日志管理介绍1.2、日志管理的重要性1.3、日志管理的组件1.4、日志管理的流程1.5、日志管理的挑战 二、日志分类介绍2.1、windows日志类别2.1.1、Application Log2.1.2、Security Log2.1.3、System Log2.1.4、Setup Log2.1.5、ForwardedEvents Lo…...
【社区投稿】给 NdArray 装上 CUDA 的轮子
Ndarry是Rust编程语言中的一个高性能多维、多类型数组库。它提供了类似 numpy 的多种多维数组的算子。与 Python 相比 Rust 生态缺乏类似 CuPy, Jax 这样利用CUDA 进行加速的开源项目。虽然 Hugging Face 开源的 candle 可以使用 CUDA backend 但是 candle 项瞄准的是大模型的相…...
Linux|Linux常用命令合集(一)
想记录一下个人会用到的一些linux命令,持续更新中… chmod\chown 之前如果文件权限不足,直接就是 chmod 777 filename/dirname ,这并不是一个好习惯。 r(读权限):值为4w(写权限)&a…...

RTPS协议之Behavior Module
目录 交互要求基本要求RTPS Writer 行为RTPS Reader行为 RTPS协议的实现与Reader匹配的Writer的行为涉及到的类型RTPS Writer实现RTPS WriterRTPS StatelessWriterRTPS ReaderLocatorRTPS StatefulWriterRTPS ReaderProxyRTPS ChangeForReader RTPS StatelessWriter BehaviorBe…...

Socket网络通讯入门(一)
提示:能力有限,不足以及错误之处还请指出! 文章目录 前言一、 计算机网络 OSI、TCP/IP、五层协议 体系结构1.OSI七层模型每层的作用2.TCP/IP协议分成3.五层协议体系结构 二、Socket服务端和客户端 简单通信1.服务端代码2.客户端 总结 前言 简…...

第十五课,海龟画图:抬笔与落笔函数、画曲线函数
一,turtle.penup()和turtle.pendown():抬起与落下画笔函数 当使用上节课学习的这个turtle.forward():画笔前进函数时,画笔会朝着当前方向在画布上留下一条指定(像素)长度的直线,但你可能发现&a…...

【机器学习】让大模型变得更聪明
文章目录 前言1. 理解大模型的局限性1.1 理解力的挑战1.2 泛化能力的挑战1.3 适应性的挑战 2. 算法创新:提高模型学习和推理能力2.1 自监督学习2.2 强化学习2.3 联邦学习 3. 数据质量与多样性:增强模型的泛化能力3.1 高质量数据的获取3.2 数据多样性的重…...

5.26机器人基础-DH参数 正解
1.建立DH坐标系 1.确定Zi轴(关节轴) 2.确定基础坐标系 3.确定Xi方向(垂直于zi和zi1的平面) 4.完全确定各个坐标系 例子: 坐标系的布局是由个人决定的,可以有不同的选择 标准坐标系布局: …...

Vue3项目练习详细步骤(第五部分:用户模块的功能)
顶部导航栏个人信息显示 接口文档 接口请求与绑定 导航栏下拉菜单功能 路由实现 退出登录和路由跳转实现 基本资料修改 页面结构 接口文档 接口请求与绑定 修改头像 页面结构 头像回显 头像上传 接口文档 重置密码 页面结构 接口文档 接口请求与绑定 顶部导航…...

测试onlyoffice在线预览文件功能
HTML示例代码 <!DOCTYPE html> <html lang"zh"><head><meta charset"UTF-8"><title>测试onlyoffice在线预览文件功能</title><script type"text/javascript" src"http://onlyoffice服务器ip:端口/…...
Day57 每日温度 + 下一个更大元素Ⅰ
739 每日温度 题目链接:739.每日温度 给定一个整数数组 temperatures ,表示每天的温度,返回一个数组 answer ,其中 answer[i] 是指对于第 i 天,下一个更高温度出现在几天后。如果气温在这之后都不会升高,…...
nuxt3 api如何透传(不引第3方库)
背景: nuxt做为一个vue的服务端渲染框架,本身就具备服务端的功能,理论上可以完整做一个系统功能,包括对数据库等等操作,但更合理的做法是nuxt应该定位只做服务端渲染的事情,更偏向ui层面,而非数据curd,业务逻辑,权限等等偏向服务端的逻辑。本身基于vue的服务端渲染已…...

list常用接口模拟实现
文章目录 一、模拟list类的框架二、函数接口实现1、迭代器接口2、常用删除、插入接口3、常用其他的一些函数接口4、默认成员函数 一、模拟list类的框架 1、使用带哨兵的双向链表实现。 2、链表结点: // List的结点类 template<class T> struct ListNode {Li…...
前端工程化工具系列(三) —— Stylelint(v16.6.1):CSS/SCSS 代码质量工具
Stylelint 是 CSS/SCSS 代码的静态分析工具,用于检查代码中的错误和样式违规。 1. 环境要求 v16 以上的 Stylelint,支持 Node.js 的版本为 v18.12.0。 在命令行中输入以下内容来查看当前系统中 node 的版本。 node -vNode.js 推荐使用 v18.20.3 或者 …...

crossover mac好用吗 CrossOver Mac怎么下载 Mac用crossover损害电脑吗
CrossOver 是一款可以让Mac用户能够自由运行和游戏windows游戏软件的虚拟机类应用,虽然能够虚拟windows但是却并不是一款虚拟机,也不需要重启系统或者启动虚拟机,类似于一种能够让mac系统直接运行windows软件的插件。它以其出色的跨平台兼容性…...
PHP模块pdo_sqlite.so: undefined symbol: sqlite3_column_table_name
安装 php-sqlite3 之后,执行php -m 命令有警告,如下 PHP Warning: PHP Startup: Unable to load dynamic library pdo_sqlite (tried: /usr/lib64/php/modules/pdo_sqlite (/usr/lib64/php/modules/pdo_sqlite: cannot open shared object file: No su…...

卷积神经网络-奥特曼识别
数据集 四种奥特曼图片_数据集-飞桨AI Studio星河社区 (baidu.com) 中间的隐藏层 已经使用参数的空间 Conv2D卷积层 ReLU激活层 MaxPool2D最大池化层 AdaptiveAvgPool2D自适应的平均池化 Linear全链接层 Dropout放置过拟合,随机丢弃神经元 -----------------…...
在软件开发中正确使用MySQL日期时间类型的深度解析
在日常软件开发场景中,时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志,到供应链系统的物流节点时间戳,时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库,其日期时间类型的…...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...
Vue记事本应用实现教程
文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展:显示创建时间8. 功能扩展:记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

如何在看板中体现优先级变化
在看板中有效体现优先级变化的关键措施包括:采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中,设置任务排序规则尤其重要,因为它让看板视觉上直观地体…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版分享
平时用 iPhone 的时候,难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵,或者买了二手 iPhone 却被原来的 iCloud 账号锁住,这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

ESP32读取DHT11温湿度数据
芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...
JVM垃圾回收机制全解析
Java虚拟机(JVM)中的垃圾收集器(Garbage Collector,简称GC)是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象,从而释放内存空间,避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢
随着互联网技术的飞速发展,消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁,不仅优化了客户体验,还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用,并…...
数据链路层的主要功能是什么
数据链路层(OSI模型第2层)的核心功能是在相邻网络节点(如交换机、主机)间提供可靠的数据帧传输服务,主要职责包括: 🔑 核心功能详解: 帧封装与解封装 封装: 将网络层下发…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比
在机器学习的回归分析中,损失函数的选择对模型性能具有决定性影响。均方误差(MSE)作为经典的损失函数,在处理干净数据时表现优异,但在面对包含异常值的噪声数据时,其对大误差的二次惩罚机制往往导致模型参数…...