1135. Is It A Red-Black Tree (30)

简介: There is a kind of balanced binary search tree named red-black tree in the data structure.

There is a kind of balanced binary search tree named red-black tree in the data structure. It has the following 5 properties:

(1) Every node is either red or black.
(2) The root is black.
(3) Every leaf (NULL) is black.
(4) If a node is red, then both its children are black.
(5) For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

For example, the tree in Figure 1 is a red-black tree, while the ones in Figure 2 and 3 are not.

Figure 1
Figure 2
Figure 3

For each given binary search tree, you are supposed to tell if it is a legal red-black tree.

Input Specification:

Each input file contains several test cases. The first line gives a positive integer K (<=30) which is the total number of cases. For each case, the first line gives a positive integer N (<=30), the total number of nodes in the binary tree. The second line gives the preorder traversal sequence of the tree. While all the keys in a tree are positive integers, we use negative signs to represent red nodes. All the numbers in a line are separated by a space. The sample input cases correspond to the trees shown in Figure 1, 2 and 3.

Output Specification:

For each test case, print in a line "Yes" if the given tree is a red-black tree, or "No" if not.

Sample Input:
3
9
7 -2 1 5 -4 -11 8 14 -15
9
11 -2 1 -7 5 -4 8 14 -15
8
10 -7 5 -6 8 15 -11 17
Sample Output:
Yes
No
No

#include <iostream>
using namespace std;
#define N 31

struct node {
    int value;
    struct node *left, *right;
};

node* buildTree(int *pre, int start, int end){
    if(start == end) return NULL;
    int i;
    for (i = start; i < end; i++)//找到比pre[start]大的第一个位置后停止 根据二叉搜索树的性质,该位置右侧的数在右子树上
        if(abs(pre[i]) > abs(pre[start])) break;
    node *root = new node();//建立"根节点"
    root->value = pre[start];
    root->left = buildTree(pre, start+1, i);//递归建立左子树
    root->right = buildTree(pre, i, end);//递归建立右子树
    return root;
}

int postOrder(node* root){//后续遍历检查路径上是否由相同的黑色节点数量
    if (root) {
        int leftBlack = postOrder(root->left);
        int rightBlack = postOrder(root->right);
        if (leftBlack < 0 || rightBlack < 0 || rightBlack != leftBlack)
            return -1;
        else if(root->value < 0)
            return leftBlack;
        else
            return leftBlack + 1;
    }
    return 0;
}

int previousOrder(node *root){//前序遍历用以检查是否有连续的两个红色节点
    if (root) {
        if (root->value < 0) {//红色节点
            if (root->left)//左节点为红色
                if (root->left->value < 0)
                    return 1;
            if (root->right)//右节点为红色
                if (root->right->value < 0)
                    return 1;
        }
        return previousOrder(root->left) || previousOrder(root->right);//递归进行检查
    }
    return 0;
}

int main(){
    int k, n, pre[N];
    cin >> k;
    for (int i = 0; i < k; i++) {
        cin >> n;
        fill(pre, pre + n, 0);
        for (int j = 0; j < n; j++) {
            cin >> pre[j];
        }
        if (pre[0] < 0) {//负号代表红色节点,不符合要求
            cout << "No\n";
            continue;
        }
        node *root = buildTree(pre, 0, n);
        //balance用来存储路径的黑色节点是否相同,非负数相同,负数(-1)代表数量不相同
        int balance = postOrder(root);
        //continous用来存储两个红色的节点是否连续,1代表连续,
        int continuous = previousOrder(root);
        //如果路径上黑色节点数量不同或者存在连续的红色节点
        if (balance < 0 || continuous == 1)
            cout << "No\n";
        else
            cout << "Yes\n";
    }
}

目录
相关文章
|
3月前
|
消息中间件 缓存 监控
MQ消息积压 / Rocketmq 积压 最全的处理方案。 (秒懂+图解+史上最全)
MQ消息积压 / Rocketmq 积压 最全的处理方案。 (秒懂+图解+史上最全)
MQ消息积压 / Rocketmq 积压 最全的处理方案。 (秒懂+图解+史上最全)
|
应用服务中间件 Linux 网络安全
Linux 安装 Nginx 并配置为系统服务(超详细)
Linux 安装 Nginx 并配置为系统服务(超详细)
|
C++
【PAT甲级 - C++题解】1135 Is It A Red-Black Tree
【PAT甲级 - C++题解】1135 Is It A Red-Black Tree
159 0
|
XML 数据格式
使用WiX Toolset创建.NET程序发布Bootstrapper(安装策略管理)(二)——自定义安装
原文: 使用WiX Toolset创建.NET程序发布Bootstrapper(安装策略管理)(二)——自定义安装 自定义产品卸载方式                继续从上一次的基础上前进,现在我们已经知道了最简单的bootstrapper打包方法,现在我们对其中的每个节点深入自定义,争取可以达到我们需要的效果。
1569 0
|
6天前
|
存储 关系型数据库 分布式数据库
PostgreSQL 18 发布,快来 PolarDB 尝鲜!
PostgreSQL 18 发布,PolarDB for PostgreSQL 全面兼容。新版本支持异步I/O、UUIDv7、虚拟生成列、逻辑复制增强及OAuth认证,显著提升性能与安全。PolarDB-PG 18 支持存算分离架构,融合海量弹性存储与极致计算性能,搭配丰富插件生态,为企业提供高效、稳定、灵活的云数据库解决方案,助力企业数字化转型如虎添翼!
|
17天前
|
弹性计算 关系型数据库 微服务
基于 Docker 与 Kubernetes(K3s)的微服务:阿里云生产环境扩容实践
在微服务架构中,如何实现“稳定扩容”与“成本可控”是企业面临的核心挑战。本文结合 Python FastAPI 微服务实战,详解如何基于阿里云基础设施,利用 Docker 封装服务、K3s 实现容器编排,构建生产级微服务架构。内容涵盖容器构建、集群部署、自动扩缩容、可观测性等关键环节,适配阿里云资源特性与服务生态,助力企业打造低成本、高可靠、易扩展的微服务解决方案。
1327 7
|
5天前
|
存储 人工智能 Java
AI 超级智能体全栈项目阶段二:Prompt 优化技巧与学术分析 AI 应用开发实现上下文联系多轮对话
本文讲解 Prompt 基本概念与 10 个优化技巧,结合学术分析 AI 应用的需求分析、设计方案,介绍 Spring AI 中 ChatClient 及 Advisors 的使用。
300 129
AI 超级智能体全栈项目阶段二:Prompt 优化技巧与学术分析 AI 应用开发实现上下文联系多轮对话
|
4天前
|
监控 JavaScript Java
基于大模型技术的反欺诈知识问答系统
随着互联网与金融科技发展,网络欺诈频发,构建高效反欺诈平台成为迫切需求。本文基于Java、Vue.js、Spring Boot与MySQL技术,设计实现集欺诈识别、宣传教育、用户互动于一体的反欺诈系统,提升公众防范意识,助力企业合规与用户权益保护。