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.
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.
For each test case, print in a line "Yes" if the given tree is a red-black tree, or "No" if not.
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
Yes No No
1 /* 2 Data: 2019-05-28 19:30:11 3 Problem: PAT_A1135#Is It A Red-Black Tree 4 AC: 01:01:28 5 6 题目大意： 7 红黑树具有如下性质的平衡二叉树： 8 1.结点非红即黑 9 2.根结点为黑色 10 3.叶子结点（空结点）为黑色 11 4.红色结点的孩子均为黑色 12 5.任意结点到叶子结点构成的简单路径所含的黑色结点数目相同 13 现给定一颗二叉树，判定其是否为红黑树 14 输入： 15 第一行给出，测试数K<=20 16 第二行给出，结点总数N<=30 17 第三行给出，先序遍历，键值均正，负数表示红色结点 18 */ 19 20 #include<cstdio> 21 #include<cmath> 22 using namespace std; 23 const int M=1e2; 24 int pre[M],ans; 25 struct node 26 { 27 int index; 28 node *lchild,*rchild; 29 }; 30 31 node* Create(node *root, int index) 32 { 33 if(!root) 34 { 35 root = new node; 36 root->index=index; 37 root->lchild=root->rchild=NULL; 38 } 39 else if(abs(pre[root->index]) > abs(pre[index])) 40 root->lchild = Create(root->lchild,index); 41 else 42 root->rchild = Create(root->rchild,index); 43 return root; 44 } 45 46 int Travel(node *root, int fa) 47 { 48 if(!ans || !root) 49 return 0; 50 int l = Travel(root->lchild,root->index); 51 int r = Travel(root->rchild,root->index); 52 if(l!=r || (pre[fa]<0&&pre[root->index]<0)){ 53 ans=0;return 0; 54 } 55 if(pre[root->index]>0) 56 l++; 57 return l; 58 } 59 60 int main() 61 { 62 #ifdef ONLINE_JUDGE 63 #else 64 freopen("Test.txt", "r", stdin); 65 #endif 66 67 int k,n; 68 scanf("%d", &k); 69 while(k--) 70 { 71 scanf("%d", &n); 72 node *root=NULL; 73 for(int i=1; i<=n; i++){ 74 scanf("%d", &pre[i]); 75 root=Create(root, i); 76 } 77 ans=1;pre[0]=-1; 78 Travel(root,0); 79 if(ans) 80 printf("Yes\n"); 81 else 82 printf("No\n"); 83 } 84 85 return 0; 86 }
PAT_A1135#Is It A Red-Black Tree
原文：https://www.cnblogs.com/blue-lin/p/10940375.html
