審題：紅黑樹是二叉樹闹丐，所以可以直接根據(jù)先序建樹(注意小于等于放在一起)
每一個(gè)節(jié)點(diǎn)到葉子結(jié)點(diǎn)的黑色的數(shù)目要相同
#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;
}
