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

### 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. 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

### 解题报告

1. 根必须时黑的。
2. 所有红节点的孩子都是黑的。
3. 任意节点到达其子孙叶子节点所有路径上黑色个数是相同的

### 代码

/*
* Problem: 1135. Is It A Red-Black Tree (30)
* Author: HQ
* Time: 2018-03-13
* State: Done
* Memo: 建树，判断是否为红黑树
*/
#include "iostream"
#include "vector"
#include "algorithm"
using namespace std;

struct Node {
int data = 0;
int blacknum;
struct Node * left = NULL;
struct Node * right = NULL;
};

int K,N;
vector<int> preOrder,inOrder;

int findIn(int x,int s,int l) {
for (int i = 0; i < l; i++) {
if (inOrder[s + i] == x)
return s + i;
}
return -1;
}

struct Node * makeTree(int s1,int s2,int n) {
struct Node * root = NULL;
int pos = findIn(preOrder[s1],s2,n);
if (pos != -1) {
root = new struct Node;
root->data = preOrder[s1];
if (pos - s2 > 0)
root->left = makeTree(s1 + 1, s2, pos - s2);
if (s2 + n - pos - 1 > 0)
root->right = makeTree(s1 + pos - s2 + 1, pos + 1, s2 + n - pos - 1);
}
return root;
}

bool cmp(int x, int y) {
return abs(x) < abs(y);
}

bool dfs(struct Node * root) {
if (root == NULL)
return true;
if (root->data < 0) {
if (root->left != NULL && root->left->data < 0)
return false;
if (root->right != NULL && root->right->data < 0)
return false;
}
bool flag = dfs(root->left) && dfs(root->right);
if (!flag)
return false;
if (root->left == NULL && root->right == NULL)
root->blacknum = (root->data > 0) ? 1 : 0;
int l = (root->left == NULL) ? 0 : root->left->blacknum;
int r = (root->right == NULL) ? 0 : root->right->blacknum;
if (l != r)
return false;
root->blacknum = l + (root->data > 0) ? 1 : 0;
return true;
}

bool check(struct Node * root) {
if (root->data < 0)
return false;
return dfs(root);
}

int main() {
cin >> K;
int x;
for (int i = 0; i < K; i++) {
cin >> N;
preOrder.clear();
inOrder.clear();
for (int j = 0; j < N; j++) {
cin >> x;
preOrder.push_back(x);
inOrder.push_back(x);
}
sort(inOrder.begin(), inOrder.end(), cmp);
struct Node * root = makeTree(0, 0, N);
if (check(root))
cout << "Yes" << endl;
else
cout << "No" << endl;
}
system("pause");
}

还没有人评论...