PAT A 급 1135

검 붉 은 나무의 특징
1. 뿌리 노드 는 검은색 입 니 다.2. 만약 에 한 노드 가 빨간색 이 라면 그의 두 노드 는 모두 빨간색 이다.3. 뿌리 노드 에서 잎 결점 까지 의 경로 에서 모든 경로 가 지나 가 는 검은색 노드 의 수 는 같다.4. 붉 은 검 은 나 무 는 이 진 트 리 입 니 다.
알고리즘
1. 뿌리 노드 가 검은색 인지 여부.2. 빨간색 노드 의 두 부분 은 모두 검은색 입 니까?3. 모든 경로 가 지나 가 는 검은색 노드 수 는 같 지 않 습 니까?

#include 
using namespace std;
vector<int> arr;

struct node
{
    int key;
    struct node *lchild,*rchild;
};

node *build(node *root,int v)
{
    if(root==NULL)
    {
        root = (node*)malloc(sizeof(node));
        root->key = v;
        root->lchild = root->rchild = NULL;
    }else if(abs(v)<=abs(root->key))
    {
        root->lchild = build(root->lchild,v);
    }else
    {
        root->rchild = build(root->rchild,v);
    }
    return root;
}

bool judge1(node *root)
{
    if(root==NULL) return true;
    if(root->key<0)
    {
        if(root->lchild!=NULL && root->lchild->key<0) return false;
        if(root->rchild!=NULL && root->rchild->key<0) return false;
    }
    return judge1(root->lchild)&&judge1(root->rchild);
}

int getBlackNum(node *root)
{
    if(root==NULL) return 0;
    int l = getBlackNum(root->lchild);
    int r = getBlackNum(root->rchild);
    return root->key>0?max(l,r)+1:max(l,r);
}

bool judge2(node *root)
{
    if(root==NULL) return true;
    int l= getBlackNum(root->lchild);
    int r = getBlackNum(root->rchild);
    if(l!=r) return false;
    return judge2(root->lchild)&&judge2(root->rchild);
}

int main()
{
    int k,n;
    scanf("%d",&k);
    for(int i=0;i<k;i++)
    {
        node *root=NULL;
        scanf("%d",&n);
        arr.resize(n);
        for(int j=0;j<n;j++)
        {
            scanf("%d",&arr[j]);
            root = build(root,arr[j]);
        }

        if(arr[0]<0 || judge1(root)==false || judge2(root)==false)
            printf("No
");
        else printf("Yes
");
    }
    return 0;

}