pat 1135

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.

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.每个叶子结点是黑色的。红黑树里面的叶子结点表示的是最下层的空结点

　　4.如果一个结点是红色的，那么它的两个孩子结点都是黑的。

　　5.从每一个结点出发，到任意叶子节点的简单路径上所包含的黑色结点个数相同。

思路：题目给定了前序遍历序列，需要注意的是红黑树是一个特殊的二叉排序树，它也符合左子树的值<根结点的值<右子树的值的特点，因此可以根据前序遍历建立一颗二叉查找树，然后判断这颗树是否为红黑树。

代码如下：

#include<cstdio>
#include<cstdlib>
#include<math.h>
#include<vector>
using namespace std; 
typedef struct node{
    int val;
    node* l;
    node* r;    
}node;
void judge2(node* root,int& mark){
    if(root->val<0){
        if(root->l!=NULL){
            if(root->l->val<0){
                mark=0;
            }
        }
        if(root->r!=NULL){
            if(root->r->val<0)
                mark=0;
        }
    }
    if(root->l!=NULL){
        judge2(root->l,mark);
    }    
}
void judge3(node* root,int count,vector<int> &v){
    if(root==NULL){
        v.push_back(count);
    }
    else{
        if(root->val>=0)
            count++;
        judge3(root->l,count,v);
        judge3(root->r,count,v);
        
    }
}
void judge(node* root){
    if(root->val<0){
        printf("No
");
        return;
    }
    int mark=1;
    judge2(root,mark);
    if(mark==0){
        printf("No
");
        return;
    }
    int count=0;
    vector<int> v;
    judge3(root,count,v);
    int sum=v[0];
    for(vector<int>::iterator it=v.begin();it!=v.end();it++){
        if(*it!=sum){
            printf("No
");
            return;
        }
    }
    printf("Yes
");
    return;
}
node* build(node* root,int val){
    if(root==NULL){
        root =(node*)malloc(sizeof(node));
        root->val=val;
        root->l=NULL;
        root->r=NULL;
         root;
    }
    else if(abs(val)<=abs(root->val)){
         root->l=build(root->l,val);
    }
    else
         root->r=build(root->r,val);
    return root;
}
int main(){
    int n,num,temp;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        node* root=NULL;
        scanf("%d",&num);
        for(int j=0;j<num;j++){
            scanf("%d",&temp);
            root=build(root,temp);
        }
        judge(root);
    }
    return 0;
}