1135 Is It A Red-Black Tree（30 分）

审题：红黑树是二叉树，所以可以直接根据先序建树(注意小于等于放在一起)
每一个节点到叶子结点的黑色的数目要相同

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
struct node {
    int data;
    node *lchild, *rchild;
};
void insert(node*&root, int x)
{
    if (root == NULL)
    {
        root = new node;
        root->data = x;
        root->lchild = root->rchild = NULL;
        return;
    }
    if (abs(x) <= abs(root->data))insert(root->lchild, x);
    else insert(root->rchild, x);
}
bool judge1(node* root)
{
    if (root == NULL)return true;
    if (root->data < 0)
    {
        if (root->lchild&&root->lchild->data < 0)return false;
        if (root->rchild&&root->rchild->data < 0)return false;
    }
    return judge1(root->lchild) && judge1(root->rchild);
}
int getheight(node* root)
{
    if (root == NULL)return 0;
    int l = getheight(root->lchild);
    int r = getheight(root->rchild);
    return root->data > 0 ? max(l, r) + 1 : max(l, r);
}
bool judge2(node* root)
{
    if (root == NULL)return true;
    int l = getheight(root->lchild);
    int r = getheight(root->rchild);
    if (l != r)return false;
    return judge2(root->lchild) && judge2(root->rchild);
}
int k, n;
vector<int>a;
int main()
{
    scanf("%d", &k);
    while (k--)
    {
        node* root = NULL;
        scanf("%d", &n);
        a.resize(n);
        bool f = true;
        for(int i=0;i<n;i++)
        {
            scanf("%d", &a[i]);
            insert(root, a[i]);
        }
        if (a[0] < 0 || judge1(root) == false || judge2(root) == false)printf("No\n");
        else printf("Yes\n");
    }
    return 0;
}