当前位置: 首页 > news >正文

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 给你一个二叉树&#xff0c;判断其是否是一个有效的二叉排序树。 有效的二叉排序树定义如下&#xff1a; 1. 结点的左子树只包含小于当前结点的数。 2. 结点的右子树只包含大于当前结点的数。 3. 所有左子树和右子树自身必须也是二叉排序树。 Input 第一行输…...

结合el-upload修改支持上传图片、视频并预览

结合element plus的el-upload标签&#xff0c;实现上传图片和视频&#xff0c;并支持在线预览和放大 1、html部分 <el-form-item label"活动照片、视频"><el-uploadv-model:file-list"state.photoList":action"state.uploadUrl"accept…...

1.SQL - 概述

1. SQL语句分类 • 数据定义语言&#xff1a;简称DDL(Data Definition Language)&#xff0c;用来定义数据库对象&#xff1a;数据库&#xff0c;表&#xff0c;列等。关键字&#xff1a;create&#xff0c;alter&#xff0c;drop等 • 数据操作语言&#xff1a;简称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++]数据结构 希尔排序

&#x1f966;前言: 希尔排序也称 “缩小增量排序”&#xff0c;它也是一种插入类排序的方法,在学习希尔排序之前我们首先了解一下直接插入排序. 一: &#x1f6a9;直接插入排序 1.1 &#x1f31f;排序思路 直接插入排序的基本原理是将一条记录插入到已排好的有序表中&#x…...

SQL进阶:子查询

一般情况下,我们都是直接对表进行查询,但有时候,想要的数据可能通过一次select 获取不到,需要嵌套select,这样就形成了子查询。 子查询可以位于查询语句的任意位置,主要的注意点在于用于不同的位置,和不同的关键字一起使用时,需要注意返回的列的数量和行的数量。 位于…...

5、IDEA集成Git

IDEA集成Git 1. 配置Git忽略文件2. 定位Git程序3. 初始化本地库、添加暂存区、提交到本地库4. 切换版本5. 创建分支和切换分支6. 合并分支7. 解决冲突 1. 配置Git忽略文件 问题1&#xff1a;为什么要忽略他们&#xff1f; 与项目的实际功能无关&#xff0c;不参与服务器上部署…...

oracle数据库sqlplus登录卡顿

问题描述 新安装了一套oracle 11.2.0.1 版本的数据库服务器&#xff0c;出现了在服务器本地通过sqlplus / as sysdba登录的时候很快&#xff0c;但是通过监听登录的时候就非常的慢&#xff0c;卡顿&#xff0c;大概需要1分钟多的时间才能登进数据库。 之前安装了好几套oracle …...

【C#】Visual Studio 2022 远程调试配置教程

在某些特殊的情况下&#xff0c;开发机和调试机可能不是同一台设备&#xff0c;此时就需要远程调试了。 开发机配置 首先需要确保两台机器在同一局域网下。 创建共享文件夹 随便找个地方新建一个文件夹&#xff0c;用来放编译结果。例如我这里是 D:\DebuggingWorkspace\。 …...

LSTM的记忆能力实验

长短期记忆网络&#xff08;Long Short-Term Memory Network&#xff0c;LSTM&#xff09;是一种可以有效缓解长程依赖问题的循环神经网络&#xff0e;LSTM 的特点是引入了一个新的内部状态&#xff08;Internal State) 和门控机制&#xff08;Gating Mechanism&#xff09;&am…...

Unity之ShaderGraph如何实现瓶装水效果

前言 有一个场景在做效果时,有一个水瓶放到桌子上的设定,但是模型只做了个水瓶,里面是空的,所以我就想办法,如何做出来瓶中装睡的效果,最好是能跟随瓶子有液体流动的效果。 如下图所示: 水面实现 水面效果 液体颜色设置 因为液体有边缘颜色和内里面颜色,所以要分开…...

【python与机器学习3】感知机和门电路:与门,或门,非门等

目录 1 电子和程序里的与门&#xff0c;非门&#xff0c;或门&#xff0c;与非门 &#xff0c;或非门&#xff0c;异或门 1.1 基础电路 1.2 所有的电路情况 1.3 电路的符号 1.4 各种电路对应的实际电路图 2 各种具体的电路 2.1 与门&#xff08;and gate&#xff09; 2…...

关键字:extends关键字

在 Java 中&#xff0c;extends 是一个关键字&#xff0c;用于表示继承关系。当一个类使用 extends 关键字时&#xff0c;它表示该类是一个子类&#xff0c;并且继承了父类的属性和方法。 以下是 extends 关键字的解析&#xff1a; 语法&#xff1a; 描述&#xff1a; ChildC…...

KEPServerEX 6 之【外篇-1】PTC-ThingWorx服务端软件安装 Tomcat10本地安装

本文目标: 安装 Java 和 Apache Tomcat ,为ThingWorx安装做基础。 ----------------------------------------------------------------------- 安装重点 --------------------------------------------------------------------- 1. 安装 Java 11 / JDK 11 添加系…...

(Mac上)使用Python进行matplotlib 画图时,中文显示不出来

【问题描述】 ①报错确缺失字体&#xff1a; ②使用matplotlib画图&#xff0c;中文字体显示不出来 【问题思考】 在网上搜了好多&#xff0c;关于使用python进行matplotlib画图字体显示不出来的&#xff0c;但是我试用了下&#xff0c;对我来说都没有。有些仅使用于windows系…...

万能刷题小程序源码系统:功能强大+试题管理+题库分类+用户列表 附带完整的搭建教程

随着互联网技术的不断进步&#xff0c;线上学习已成为越来越多人的选择。刷题作为提高学习效果的重要方式&#xff0c;一直受到广大学生的喜爱。然而&#xff0c;市面上的刷题软件虽然繁多&#xff0c;但功能各异&#xff0c;质量参差不齐&#xff0c;使得很多用户在选择时感到…...

5.2 显示窗口的内容(二)

三,显示器几何形状管理 只有显示管理器被允许更改显示器的几何形状。窗口管理器也是显示管理器。 3.1 当显示器显示其自身内容时 当显示器显示其自身内容时,适用以下属性: 显示属性描述SCREEN_PROPERTY_PROTECTION_ENABLE表示显示目标窗口是否需要内容保护。只要显示器上…...

SpringCloud 整合 Canal+RabbitMQ+Redis 实现数据监听

1Canal介绍 Canal 指的是阿里巴巴开源的数据同步工具&#xff0c;用于数据库的实时增量数据订阅和消费。它可以针对 MySQL、MariaDB、Percona、阿里云RDS、Gtid模式下的异构数据同步等情况进行实时增量数据同步。 当前的 canal 支持源端 MySQL 版本包括 5.1.x , 5.5.x , 5.6.…...

web vue 项目 Docker化部署

Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段&#xff1a; 构建阶段&#xff08;Build Stage&#xff09;&#xff1a…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

拉力测试cuda pytorch 把 4070显卡拉满

import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试&#xff0c;通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小&#xff0c;增大可提高计算复杂度duration: 测试持续时间&#xff08;秒&…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...

管理学院权限管理系统开发总结

文章目录 &#x1f393; 管理学院权限管理系统开发总结 - 现代化Web应用实践之路&#x1f4dd; 项目概述&#x1f3d7;️ 技术架构设计后端技术栈前端技术栈 &#x1f4a1; 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 &#x1f5c4;️ 数据库设…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...

Docker 本地安装 mysql 数据库

Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker &#xff1b;并安装。 基础操作不再赘述。 打开 macOS 终端&#xff0c;开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...