PAT1135 Is It A Red-Black Tree（红黑树）

题意：

给出一棵平衡二叉搜索树的先序序列，要求判断是否为红黑树

思路：

这题一开始我没意识到红黑树都是平衡二叉搜索树，知道后就先按照先序和中序建树，然后按照红黑树的定义，用递归判断每个节点的左右黑节点的个数即可

#include <bits/stdc++.h>
using namespace std;
const int maxn=50;
int pre[maxn],in[maxn];struct node{int key;node *left,*right;
};node * buildTree(int l,int r,int ll,int rr){if(l>r||ll>rr){return nullptr;}node *root=new node();int pos;for(pos=ll;pos<rr&&pre[l]!=in[pos];pos++);int numleft=pos-ll;int numright=rr-pos;root->key=pre[l];root->left=buildTree(l+1,l+numleft,ll,pos-1);root->right=buildTree(r-numright+1,r,pos+1,rr);return root;
}
bool cmp(int a,int b){return abs(a)<abs(b);
}int check(node *root){if(!root)return 1;if(root->key<0){if(root->left&&root->left->key<0){return -1;}if(root->right&&root->right->key<0){return -1;}}int numleft=check(root->left);int numright=check(root->right);if(numright==-1||numleft==-1){return -1;}if(numleft==numright){if(root->key<0)return numleft;elsereturn numleft+1;}else{return -1;}
}int main(){int k,n;scanf("%d",&k);while(k--){scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&pre[i]);in[i]=pre[i];}if(pre[0]<0){printf("No\n");continue;}sort(in,in+n,cmp);node *root=buildTree(0,n-1,0,n-1);if(check(root)!=-1){printf("Yes\n");}else{printf("No\n");}}return 0;
}