F (1164) : B DS二叉排序树_有效的二叉排序树
Description
给你一个二叉树,判断其是否是一个有效的二叉排序树。
有效的二叉排序树定义如下:
1. 结点的左子树只包含小于当前结点的数。
2. 结点的右子树只包含大于当前结点的数。
3. 所有左子树和右子树自身必须也是二叉排序树。
Input
第一行输入t,表示有t个二叉树。
第二行起,每一行首先输入n,接着输入n个整数,代表二叉树。
以此类推共输入t个二叉树。
数组形式的二叉树表示方法与题目:DS二叉树_伪层序遍历构建二叉树 相同,输入-1表示空结点。
Output
每一行输出当前二叉树是否为二叉排序树,若是,则输出true,否则输出false。
共输出t行。
Input
4
3 2 1 3
7 5 1 4 -1 -1 3 6
7 2 1 4 -1 -1 3 6
8 9 8 -1 7 -1 6 -1 5
Output
true
false
true
true
代码如下,难点在于两个,一个是非递归层次遍历建树,第二个是判断为有效的二叉排序树。
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h> // 使用 INT_MIN 来初始化 pre#define MAXN 1005typedef struct Node
{int data;struct Node *Lchild;struct Node *Rchild;
} Node;Node *Build_Level(int *a, int num)
{Node *ROOT = NULL; // 待会要把根节点返回Node *queue[MAXN]; // 队列int front = 0, rear = 0;int k = 0;int ch;ch = a[k];k++;if (ch != -1){Node *root = (Node *)malloc(sizeof(Node));root->data = ch;root->Lchild = NULL;root->Rchild = NULL;ROOT = root;queue[rear++] = ROOT;}while (front != rear && k < num){Node *s = queue[front];front++;ch = a[k];if (ch != -1 && k < num){Node *news = (Node *)malloc(sizeof(Node));news->data = ch;news->Lchild = NULL;news->Rchild = NULL;s->Lchild = news;queue[rear++] = news;}k++;ch = a[k];if (ch != -1 && k < num){Node *news = (Node *)malloc(sizeof(Node));news->data = ch;news->Lchild = NULL;news->Rchild = NULL;s->Rchild = news;queue[rear++] = news;}k++;}return ROOT;
}bool JudgeBst(Node *T, int *pre)
{ // 判断是否为 BSTif (T == NULL){return true;}if (!JudgeBst(T->Lchild, pre)){return false;}if (T->data < *pre){return false;}*pre = T->data;return JudgeBst(T->Rchild, pre);
}int main()
{int t;int sum;scanf("%d", &t);while (t--){scanf("%d", &sum);int *array = (int *)malloc(sizeof(int) * sum);for (int i = 0; i < sum; i++){scanf("%d", &array[i]);}Node *p = Build_Level(array, sum); // p 为根节点int pre = INT_MIN; // 初始化 pre 为负无穷printf("%s\n", (JudgeBst(p, &pre) ? "true" : "false"));free(array);}return 0;
}
相关文章:
F (1164) : B DS二叉排序树_有效的二叉排序树
Description 给你一个二叉树,判断其是否是一个有效的二叉排序树。 有效的二叉排序树定义如下: 1. 结点的左子树只包含小于当前结点的数。 2. 结点的右子树只包含大于当前结点的数。 3. 所有左子树和右子树自身必须也是二叉排序树。 Input 第一行输…...
结合el-upload修改支持上传图片、视频并预览
结合element plus的el-upload标签,实现上传图片和视频,并支持在线预览和放大 1、html部分 <el-form-item label"活动照片、视频"><el-uploadv-model:file-list"state.photoList":action"state.uploadUrl"accept…...
1.SQL - 概述
1. SQL语句分类 • 数据定义语言:简称DDL(Data Definition Language),用来定义数据库对象:数据库,表,列等。关键字:create,alter,drop等 • 数据操作语言:简称DML(Data …...
GaussDB数据库表创建行访问控制策略
目录 一、前言 二、GaussDB中的行访问控制 1、CREATE ROW LEVEL SECURITY POLICY语法 2、ALTER ROW LEVEL SECURITY POLICY语法 3、ROW LEVEL SECURITY策略与适配SQL语法关系 三、GaussDB中的行访问控制策略示例 1、实现GaussDB行访问控制的一般步骤 2、行访问控制策略…...
提升设备巡检效率的关键:易点易动设备管理系统的应用
随着互联网技术的发展,智慧设备管理已成为各行各业提升运营效率的重要选择。相比传统的手动巡检方式,采用设备管理系统可以实现物联网技术给企业带来更高效的运营方式。其中,易点易动作为一款成熟的设备管理系统,其广泛应用于提升设备巡检效率这一领域发挥了很好的作用。 采用易…...
【C++】STL 容器 - list 双向链表容器 ① ( 容器特点 | 容器操作时间复杂度 | 构造函数 )
文章目录 一、 list 双向链表容器简介1、容器特点2、容器操作时间复杂度3、遍历访问5、头文件 二、 list 双向链表容器 构造函数1、默认无参构造函数2、创建包含 n 个相同元素的 list 双向链表3、使用初始化列表构造 list 双向链表4、使用另外一个 list 容器 构造 list 双向链表…...
[C/C++]数据结构 希尔排序
🥦前言: 希尔排序也称 “缩小增量排序”,它也是一种插入类排序的方法,在学习希尔排序之前我们首先了解一下直接插入排序. 一: 🚩直接插入排序 1.1 🌟排序思路 直接插入排序的基本原理是将一条记录插入到已排好的有序表中&#x…...
SQL进阶:子查询
一般情况下,我们都是直接对表进行查询,但有时候,想要的数据可能通过一次select 获取不到,需要嵌套select,这样就形成了子查询。 子查询可以位于查询语句的任意位置,主要的注意点在于用于不同的位置,和不同的关键字一起使用时,需要注意返回的列的数量和行的数量。 位于…...
5、IDEA集成Git
IDEA集成Git 1. 配置Git忽略文件2. 定位Git程序3. 初始化本地库、添加暂存区、提交到本地库4. 切换版本5. 创建分支和切换分支6. 合并分支7. 解决冲突 1. 配置Git忽略文件 问题1:为什么要忽略他们? 与项目的实际功能无关,不参与服务器上部署…...
oracle数据库sqlplus登录卡顿
问题描述 新安装了一套oracle 11.2.0.1 版本的数据库服务器,出现了在服务器本地通过sqlplus / as sysdba登录的时候很快,但是通过监听登录的时候就非常的慢,卡顿,大概需要1分钟多的时间才能登进数据库。 之前安装了好几套oracle …...
【C#】Visual Studio 2022 远程调试配置教程
在某些特殊的情况下,开发机和调试机可能不是同一台设备,此时就需要远程调试了。 开发机配置 首先需要确保两台机器在同一局域网下。 创建共享文件夹 随便找个地方新建一个文件夹,用来放编译结果。例如我这里是 D:\DebuggingWorkspace\。 …...
LSTM的记忆能力实验
长短期记忆网络(Long Short-Term Memory Network,LSTM)是一种可以有效缓解长程依赖问题的循环神经网络.LSTM 的特点是引入了一个新的内部状态(Internal State) 和门控机制(Gating Mechanism)&am…...
Unity之ShaderGraph如何实现瓶装水效果
前言 有一个场景在做效果时,有一个水瓶放到桌子上的设定,但是模型只做了个水瓶,里面是空的,所以我就想办法,如何做出来瓶中装睡的效果,最好是能跟随瓶子有液体流动的效果。 如下图所示: 水面实现 水面效果 液体颜色设置 因为液体有边缘颜色和内里面颜色,所以要分开…...
【python与机器学习3】感知机和门电路:与门,或门,非门等
目录 1 电子和程序里的与门,非门,或门,与非门 ,或非门,异或门 1.1 基础电路 1.2 所有的电路情况 1.3 电路的符号 1.4 各种电路对应的实际电路图 2 各种具体的电路 2.1 与门(and gate) 2…...
关键字:extends关键字
在 Java 中,extends 是一个关键字,用于表示继承关系。当一个类使用 extends 关键字时,它表示该类是一个子类,并且继承了父类的属性和方法。 以下是 extends 关键字的解析: 语法: 描述: ChildC…...
KEPServerEX 6 之【外篇-1】PTC-ThingWorx服务端软件安装 Tomcat10本地安装
本文目标: 安装 Java 和 Apache Tomcat ,为ThingWorx安装做基础。 ----------------------------------------------------------------------- 安装重点 --------------------------------------------------------------------- 1. 安装 Java 11 / JDK 11 添加系…...
(Mac上)使用Python进行matplotlib 画图时,中文显示不出来
【问题描述】 ①报错确缺失字体: ②使用matplotlib画图,中文字体显示不出来 【问题思考】 在网上搜了好多,关于使用python进行matplotlib画图字体显示不出来的,但是我试用了下,对我来说都没有。有些仅使用于windows系…...
万能刷题小程序源码系统:功能强大+试题管理+题库分类+用户列表 附带完整的搭建教程
随着互联网技术的不断进步,线上学习已成为越来越多人的选择。刷题作为提高学习效果的重要方式,一直受到广大学生的喜爱。然而,市面上的刷题软件虽然繁多,但功能各异,质量参差不齐,使得很多用户在选择时感到…...
5.2 显示窗口的内容(二)
三,显示器几何形状管理 只有显示管理器被允许更改显示器的几何形状。窗口管理器也是显示管理器。 3.1 当显示器显示其自身内容时 当显示器显示其自身内容时,适用以下属性: 显示属性描述SCREEN_PROPERTY_PROTECTION_ENABLE表示显示目标窗口是否需要内容保护。只要显示器上…...
SpringCloud 整合 Canal+RabbitMQ+Redis 实现数据监听
1Canal介绍 Canal 指的是阿里巴巴开源的数据同步工具,用于数据库的实时增量数据订阅和消费。它可以针对 MySQL、MariaDB、Percona、阿里云RDS、Gtid模式下的异构数据同步等情况进行实时增量数据同步。 当前的 canal 支持源端 MySQL 版本包括 5.1.x , 5.5.x , 5.6.…...
Zustand 状态管理库:极简而强大的解决方案
Zustand 是一个轻量级、快速和可扩展的状态管理库,特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...
理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端
🌟 什么是 MCP? 模型控制协议 (MCP) 是一种创新的协议,旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议,它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...
系统设计 --- MongoDB亿级数据查询优化策略
系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log,共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题,不能使用ELK只能使用…...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...
汇编常见指令
汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX(不访问内存)XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...
(转)什么是DockerCompose?它有什么作用?
一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用,而无需手动一个个创建和运行容器。 Compose文件是一个文本文件,通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...
【51单片机】4. 模块化编程与LCD1602Debug
1. 什么是模块化编程 传统编程会将所有函数放在main.c中,如果使用的模块多,一个文件内会有很多代码,不利于组织和管理 模块化编程则是将各个模块的代码放在不同的.c文件里,在.h文件里提供外部可调用函数声明,其他.c文…...
欢乐熊大话蓝牙知识17:多连接 BLE 怎么设计服务不会乱?分层思维来救场!
多连接 BLE 怎么设计服务不会乱?分层思维来救场! 作者按: 你是不是也遇到过 BLE 多连接时,调试现场像网吧“掉线风暴”? 温度传感器连上了,心率带丢了;一边 OTA 更新,一边通知卡壳。…...
第14节 Node.js 全局对象
JavaScript 中有一个特殊的对象,称为全局对象(Global Object),它及其所有属性都可以在程序的任何地方访问,即全局变量。 在浏览器 JavaScript 中,通常 window 是全局对象, 而 Node.js 中的全局…...
基于django+vue的健身房管理系统-vue
开发语言:Python框架:djangoPython版本:python3.8数据库:mysql 5.7数据库工具:Navicat12开发软件:PyCharm 系统展示 会员信息管理 员工信息管理 会员卡类型管理 健身项目管理 会员卡管理 摘要 健身房管理…...
