PAT甲级：A1135 Is It A Red-Black Tree (30分)

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:

1
2
3
4
5
6
7
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:

1
2
3
Yes
No
No

  • 题意：题目给出了红黑树的定义：

    • （1）每个节点都是红色或黑色。
    • （2）根是黑色的。
    • （3）每片叶子（NULL）是黑色的。
    • （4）如果节点为红色，则其两个子节点均为黑色。
    • （5）对于每个节点，从节点到后代叶子的所有简单路径都包含相同数量的黑色节点。

    通过红黑树的定义判断给出的二叉搜索树是不是红黑树；所有结点值都是正整数，用正负号表示颜色（负号为红色）。

  • 分析：这道题实际上考察的不是红黑树，要不然甲级就超纲啦，哈哈。题目给了二叉搜索树的先序遍历序列，先根据BST的特性建树（链式存储）。之后判断，如果根是红色则不是红黑树，否则就从根节点开始深度优先，在途中如果发现某个结点是红色，其孩子也出现红色，则把 isrbt标记为false，同时传入参数cnt记录从根节点到叶子结点上黑色结点的个数，当到达递归边界的时候（即空结点）判断从根节点到当前位置上的黑色结点数cnt是不是和之前记录过的cntBlack相等，如果不等则标记isrbt为false，但如果之前没记录过cntBlack（即cntBlack为-1）则不作判断。

注意：1. 插入结点时，传入的root需要使用引用类型。2. 因为有多个序列要判断，所以每次DFS前都要重置isrbt和cntBlack。

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
#include <bits/stdc++.h>
using namespace std;
struct node {
    int data;
    node *left, *right;
    node(int x) : data(x) { left = right = NULL; }
};
void insert(node* &root, int x) {
    if (root == NULL) {
        root = new node(x);
        return;
    }
    if (abs(x) < abs(root->data)) insert(root->left, x);
    else insert(root->right, x);
}
bool isrbt;
int cntBlack = -1;
void dfs(node* root, int cnt) {
    if (root == NULL) {
        if (cntBlack == -1) cntBlack = cnt;
        else if (cntBlack != cnt) isrbt = false;
        return;
    }
    if (root->data < 0) {
        if (root->left != NULL && root->left->data < 0) isrbt = false;
        if (root->right != NULL && root->right->data < 0) isrbt = false;
    }
    dfs(root->left, root->data > 0 ? cnt + 1 : cnt);
    dfs(root->right, root->data > 0 ? cnt + 1 : cnt);
}
int main() {
    int k, n, x;
    scanf("%d", &k);
    while (k--) {
        scanf("%d", &n);
        node* root = NULL;
        for (int i = 0; i < n; i++) {
            scanf("%d", &x);
            insert(root, x);
        }
        if (root->data < 0) printf("No\n");
        else {
            isrbt = true;
            cntBlack = -1;
            dfs(root, 0);
            printf("%s\n", isrbt ? "Yes" : "No");
        }
    }
    return 0;
}