leetcode 958.二叉树的完全性检验

1.题目要求:

给你一棵二叉树的根节点 root ,请你判断这棵树是否是一棵 完全二叉树 。在一棵 完全二叉树 中,除了最后一层外,所有层都被完全填满,并且最后一层中的所有节点都尽可能靠左。最后一层(第 h 层)中可以包含 12h 个节点。

在这里插入图片描述

2.题目代码:

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*///创建队列
typedef struct queue{struct TreeNode* data;struct queue* next;
}queue_t;
//入队
void push(queue_t** head,struct TreeNode* data){queue_t* newnode = (queue_t*)malloc(sizeof(queue_t));newnode->data = data;newnode->next = NULL;if(*head == NULL){*head = newnode;return;}queue_t* tail = *head;while(tail->next != NULL){tail = tail->next;}tail->next = newnode;
}
//出队
struct TreeNode* pop(queue_t** head){struct TreeNode* x = (*head)->data;(*head) = (*head)->next;return x; 
}
bool isCompleteTree(struct TreeNode* root) {int node_count = 0;//设置结点个数int* level_travel_node = (int*)malloc(sizeof(int) * 200);//记录最后一层的标记数组int j = 0;int depth = 0;queue_t* quence = NULL;int count = 1;int nextcount =  0;int size = 0;//层序遍历开始push(&quence,root);size++;node_count++;while(size != 0){depth++;for(int i = 0;i < count;i++){struct TreeNode* temp = pop(&quence);size--;if(temp->left != NULL){push(&quence,temp->left);size++;node_count++;nextcount++;}if(temp->right != NULL){push(&quence,temp->right);size++;node_count++;nextcount++;}}count = nextcount;nextcount = 0;}//判断结点数,如果节点数为1,则直接返回trueif(node_count == 1){return true;}else{//如果节点数不为1,则判断结点总数是否符合完全二叉树的结点范围,不符合直接返回falseif(node_count >= (int)pow(2,depth -1)&&node_count <= ((int)pow(2,depth) - 1)){printf("%d ",node_count);int depth_t = 0;size = 0;count = 1;int remove_line_count = 0;//记录除最后一行的节点数量nextcount = 0;push(&quence,root);size++;remove_line_count++;//再次进行层序遍历,一直遍历到倒数第二次位置while(size != 0){depth_t++;//判断是否为倒数第二层 if(depth_t != depth - 1){for(int i = 0;i < count;i++){struct TreeNode* temp = pop(&quence);size--;if(temp->left != NULL){push(&quence,temp->left);size++;remove_line_count++;nextcount++;}if(temp->right != NULL){push(&quence,temp->right);size++;remove_line_count++;nextcount++;}}count = nextcount;nextcount = 0;}else{//是倒数第二层后,把最后一层的结点进行记录,如果为空为-1,不为空为1for(int i = 0;i < count;i++){struct TreeNode* temp = pop(&quence);size--;if(temp->left != NULL){level_travel_node[j] = 1;j++;}else{level_travel_node[j] = -1;j++;}if(temp->right != NULL){level_travel_node[j] = 1;j++;}else{level_travel_node[j] = -1;j++;}}break;}}//判断除最后一层的结点数量,如果不对,则返回falseif(remove_line_count != ((int)pow(2,depth - 1) - 1)){return false;}else{int i = 0;for(i = 0;i < j;i++){if(level_travel_node[i] == -1){break;}}//如果-1后的结点有1,则为错,如果不是则为trueint j_1 = i + 1;for(j_1 = i + 1;j_1 < j;j_1++){if(level_travel_node[j_1] == 1){return false;}}return true;}}else{return false;}}
}

解题步骤都在代码里了,虽然比较繁琐,但如果大家觉得好的话,可以给个免费的赞吗,谢谢了^ _ ^

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

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

相关文章

YOLOv8改进 | 主干网络 | 将backbone替换为MobileNetV4【小白必备教程+附完整代码】

秋招面试专栏推荐 &#xff1a;深度学习算法工程师面试问题总结【百面算法工程师】——点击即可跳转 &#x1f4a1;&#x1f4a1;&#x1f4a1;本专栏所有程序均经过测试&#xff0c;可成功执行&#x1f4a1;&#x1f4a1;&#x1f4a1; 专栏目录 &#xff1a;《YOLOv8改进有效…

Linux PCI和PCIe总线

1 PCIe中断 - PCI/PCIe设备中断都是level触发&#xff0c;并且请求信号为低电平有效 - PCI总线一般只有INTA#到INTD#的4个中断引脚&#xff0c;所以PCI多功能设备的func一般不会超过4个&#xff0c;但是共享中断除外 2 IOMMU 2.1 ARM SMMU v2 Refer to my blog ARM SMMU v2. 2.…

【机器学习】重塑游戏世界:机器学习如何赋能游戏创新与体验升级

&#x1f4dd;个人主页&#x1f339;&#xff1a;Eternity._ &#x1f339;&#x1f339;期待您的关注 &#x1f339;&#x1f339; ❀目录 &#x1f50d;1. 引言&#xff1a;游戏世界的变革前夜&#x1f4d2;2. 机器学习驱动的游戏创新&#x1f31e;智能化游戏设计与开发&…

OJ-0807

题目 参考 import java.util.ArrayList; import java.util.List; import java.util.Objects; import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in new Scanner(System.in);String input in.nextLine();String[] numStrs inp…

身体出现这5种异常,可能是甲状腺在求救,千万别扛着!

甲状腺&#xff0c;被誉为人体新陈代谢的“发动机”&#xff0c;是调节我们身体能量和代谢的重要器官。然而&#xff0c;当甲状腺出现问题时&#xff0c;它往往会通过身体的一些异常信号向我们求救。北京精诚博爱医院张维一主任提醒&#xff1a;以下是五种常见的甲状腺异常表现…

您知道Jmeter中Redirect Automatically 和 Follow Redirects的使用场景吗?

相信很多使用过jmeter的同学都没有关注过请求中的Redirect Automatically 和 Follow Redirects选项&#xff0c;如下图&#xff1a; 在 JMeter 中&#xff0c;Redirect Automatically 和 Follow Redirects 是与 HTTP 请求重定向相关的两个选项&#xff0c;它们之间是有很大区别…

速度规划之:起点速度和终点速度不为零的非对称梯形速度规划

起点速度和终点速度不为零的非对称梯形速度规划 一、引言二、理论基础1. 梯形速度规划概述2.数学建模- 变量定义- 约束关系- 公式推导 三、计算过程1.只存在减速段2.只存在加速段3.存在加速段和减速段4.存在加速度段、匀速段和减速段 四、仿真实现五、优缺点优点缺点 六、总结 …

亚马逊等跨境电商平台怎么找到好的测评资源?

如何找到好的测评资源呢&#xff1f; 目前常规卖家找测评资源主要通过以下途径&#xff1a; 联系自己在海外的亲友帮忙测评&#xff0c;不过海外的亲友会比较有限安排业务员在facebook等社交平台找老外测评&#xff0c;但社交平台找老外很难掌控留评时效&#xff0c;甚至会遇…

破解USB设备通讯协议实现自定义软件控制的步骤与方法

在设备和计算机之间通过USB进行通讯的情况下&#xff0c;厂家提供的软件可以控制设备&#xff0c;但没有提供任何其他资料和支持&#xff0c;这种情况下&#xff0c;若希望自行开发软件来实现同样的功能&#xff0c;可以通过以下步骤破解通讯协议并开发自定义程序。 1. 捕获US…

2-57 基于matlab 实现了气缸的充气和放气的仿真

基于matlab 实现了气缸的充气和放气的仿真&#xff0c;在等温情况和绝热两种情况下分别进行了仿真&#xff0c;并给多变过程下的理论计算公式。程序已调通&#xff0c;可直接运行。 2-57 matlab 气缸充气和放气仿真 - 小红书 (xiaohongshu.com)

【论文阅读】PETRv2: A Unified Framework for 3D Perception from Multi-Camera Images

Q: 论文如何解决这个问题&#xff1f; A: 论文通过提出PETRv2框架来解决多相机图像的3D感知问题&#xff0c;具体方法包括以下几个关键点&#xff1a; 时间建模&#xff08;Temporal Modeling&#xff09;&#xff1a; 通过3D坐标对齐&#xff08;3D Coordinates Alignment&…

ASP.Net Core设置接口根路径的方法

使用asp.net core开发微服务项目&#xff0c;需要给每个服务设置不同的根路径&#xff0c;这样既能使用网关转发请求&#xff0c;又方便对单个服务进行测试&#xff0c;保证请求路径的统一。 设置方法需要使用中间件&#xff0c;在Program.cs添加如下代码 app.UsePathBase(&qu…

通过ZRender画一个大屏的顶部样式标题

介绍&#xff1a;通过ZRender画一个大屏项目的顶部样式&#xff0c;在其中放入大屏的标题。ZRender 是二维绘图引擎&#xff0c;它提供 Canvas、SVG、VML 等多种渲染方式。ZRender 也是 ECharts 的渲染器。 一、下载 npm install zrender终端输入以上命令下载包即可。 二、导…

记忆化搜索——1

目录 1.斐波那契数 2.不同路径 3.最长递增子序列 4.猜数字大小2 5.矩阵中的最长递增路径 1.斐波那契数 该题规律很明显&#xff0c;就直接放记忆化搜索的版本了 class Solution { public:int dfs(int n){if(n0||n1)//递归出口{return n;}if(f[n-1]-1)//检查是否已经记忆过…

JVM 加载阶段 Class对象加载位置是在 堆中还是方法区?

在JVM&#xff08;Java虚拟机&#xff09;的类加载过程中&#xff0c;Class对象的加载位置涉及到堆&#xff08;Heap&#xff09;和方法区&#xff08;Method Area&#xff09;两个关键区域。具体来说&#xff0c;类的加载阶段涉及到将类的.class文件中的二进制数据读入到内存中…

黑丝或者白丝,都可以用LoRA(Stable Diffusion进阶篇:ComfyUI 附加网络)

前言 在学习WebUI的那些基础知识点的时候&#xff0c;有一个东西是每一个初学者都绕不开的大山-附加网络。 这个东西对于每一个接触Stable Diffusion的小伙伴来说就像是小学门口小卖部卖的辣条、初中课本上的涂鸦、高中数学卷解不开的最后一道大题。 学习过WebUI里Stable Di…

揭秘亚马逊新手快速成长背后的秘密:从入门到精通

在亚马逊这个充满机遇与挑战的市场平台上&#xff0c;作为一名深耕多年的卖家&#xff0c;我积累了宝贵的经验和见解。随着市场环境的不断变化&#xff0c;我意识到&#xff0c;无论是新加入的创业者还是经验丰富的老手&#xff0c;都需要不断学习和适应&#xff0c;以在这个平…

游戏行业报告(一)| 中国占全球头部上市游戏企业34%,“智能NPC”竞争方向较受关注

近日&#xff0c;伽马数据发布了《2024中国上市/非上市游戏企业竞争力报告》&#xff0c;本篇文章仅采用《2024中国上市/非上市游戏企业竞争力报告》的部分数据。由于文章太长&#xff0c;所以分了下集&#xff0c;大家可以收藏关注~ 企业全球资本市场竞争现状 全球TOP50上市游…

Motionface ai工具有哪些?

Motionface Android/PC 用一张静态含有人脸相片来生成一个能说会唱的虚拟主播。使用简单便捷&#xff0c;极致的流畅度体验超乎您的想象。 免费下载 Respeak PC电脑软件 任意视频一键生成虚拟主播&#xff0c;匹配音频嘴型同步&#xff0c;保留原视频人物神态和动作&#xff0c…

什么是柔性生产?

柔性生产&#xff0c;是一种能够迅速调整生产流程、产品种类及产量&#xff0c;以低成本、高效率响应市场多样化需求的生产方式。它不仅仅是对生产线硬件的升级&#xff0c;更是对生产组织、管理模式及信息技术的全面革新。柔性生产的核心在于“灵活”二字&#xff0c;即企业能…