PAT甲级1135Is It A Red-Black Tree

Posted on | | Visitors:
Words count in article: 657 字 | Reading time ≈ 3 分

题目链接

https://pintia.cn/problem-sets/994805342720868352/problems/994805346063728640

题解

题目要求

  • 红黑树

    在二叉搜索树的基础上，红黑树还具有以下特征

    1. 每个结点是红色或者黑色

    2. 根结点是黑色的

    3. 叶子结点（NULL）都是黑色

    4. 每个红色结点的两个子结点都是黑色

      从每个叶子到根的所有路径上不能有两个连续的红色结点

    5. 每个结点到其每个叶子结点的所有路径都包含相同数目的黑色节点。

给定一颗二叉搜索树，请判断它是否是一个合法的红黑树。

  • 输入

    • K：正整数，不超过30，测试用例的数量
    • N：正整数，不超过30，二叉树中结点的数量
    • 二叉树的先序遍历结果：结点的值都是正整数，用负数代表红色结点

  • 输出

    判断每颗二叉搜索树是否是红黑树，是则输出Yes，否则输出No。

解题思路

  1. 根据先序遍历结果和二叉搜索树的性质（左子树小于根结点小于右子树），递归构建二叉树
  2. 判断性质3：根结点是否是黑色
  3. 判断性质4，见代码中的函数judge1
  4. 判断性质5，见代码中的函数judge2

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
// Problem: PAT Advanced 1135
// URL: https://pintia.cn/problem-sets/994805342720868352/problems/994805346063728640
// Tags: Tree BST RBTree

#include <iostream>
#include <cmath>
using namespace std;

struct Node{
    int val;
    Node* left = nullptr;
    Node* right = nullptr;
};

Node* build(Node* root, int v){
    if (root == nullptr){
        root = new Node();
        root->val = v;
    }
    else if (abs(v) <= abs(root->val))
        root->left = build(root->left, v);
    else
        root->right = build(root->right, v);
    return root;
}

bool judge1(Node* root){
    if (root == nullptr)
        return true;
    if (root->val < 0){
        if (root->left != nullptr && root->left->val < 0)
            return false;
        if (root->right != nullptr && root->right->val < 0)
            return false;
    }
    return judge1(root->left) && judge1(root->right);
}

int getDepth(Node* root){
    if (root == nullptr)
        return 0;
    int ret = max(getDepth(root->left), getDepth(root->right));
    return root->val > 0 ? ret + 1 : ret;
}

bool judge2(Node *root){
    if (root == nullptr) return true;
    if (getDepth(root->left) != getDepth(root->right))
        return false;
    return judge2(root->left) && judge2(root->right);
}

int main()
{
    int k, n, val;
    scanf("%d", &k);
    while (k--){
        scanf("%d", &n);
        Node* root = nullptr;
        for (int i = 0; i < n; i++){
            scanf("%d", &val);
            root = build(root, val);
        }
        if (root->val < 0 || !judge1(root) || !judge2(root))
            printf("No\n");
        else
            printf("Yes\n");
    }
    return 0;
}

参考链接

https://blog.csdn.net/liuchuo/article/details/78037334

作者：@臭咸鱼

转载请注明出处：https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!