PAT甲级1135.

目录

A1135

题目

样例

输入:

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

思路和坑点

　　柳神赛高！我只能看懂并理解柳神的代码，自己暂时还写不出来，具体可以看看注释。

AC代码

#include<bits/stdc++.h>
using namespace std; 
typedef struct node{
    int data;
    struct node *left,*right;
}Node,*Tree; 
void Insert(Node *&root,int x){             //插入建树 
    if(root==NULL){
        root=new Node;
        root->data=x;
        root->right=root->left=NULL;
    }
    else if(abs(x)<=abs(root->data))        //插入左子树 
        Insert(root->left,x);        
    else Insert(root->right,x);             //插入右子树 
}
bool JudgeRB(Tree root ){                   //判断是否符合红黑结点要求 
    if(root==NULL) return true;
    if(root->data<0){                       //如果是红结点，判断孩子 
        if(root->left&&root->left->data<0)    return false; 
        if(root->right&&root->right->data<0)    return false;
    }
    return JudgeRB(root->left)&&JudgeRB(root->right);    //判断左右子树是否都符合红黑标准 
}
int getBnum(Tree root){
    if(root==NULL) return 0;
    int l=getBnum(root->left);
    int r=getBnum(root->right);
    if(root->data>0)
        return max(l,r)+1;                  //如果当前结点是黑色，返回左右子树最大值+1 
    else
        return max(l,r);                    //如果是红色，返回左右子树的最大值 
}
bool JudgeBnum(Tree root){                  //判断左右子树一直到叶子结点路径上黑色结点的个数是否相同 
    if(root==NULL) return true;
    int l=getBnum(root->left);
    int r=getBnum(root->right);
    if(l!=r) return false;
    return JudgeBnum(root->left)&&JudgeBnum(root->right);
} 
int main(){    
#ifdef ONLINE_JUDGE    
#else    
    freopen("1.txt", "r", stdin);    
#endif    
    int k,n;
    scanf("%d",&k);
    for(int i=0;i<k;i++){
        scanf("%d",&n);
        vector<int> a(n);
        Tree root=NULL;
        for(int j=0;j<n;j++){
            scanf("%d",&a[j]);
            Insert(root,a[j]);
        }
        if(a[0]<0||JudgeBnum(root)==false||JudgeRB(root)==false)
            puts("No");
        else
            puts("Yes");
    }
    return 0;    
}