题目链接：点击打开链接
题目大意：给一棵二叉搜索树的前序遍历，判断它是否为红黑树，是输出Yes，否则输出No。
解题思路：
判断以下几点：
- 根结点是否为黑色；
- 如果一个结点是红色，它的孩子节点是否都为黑色；
- 从任意结点到叶子结点的路径中，黑色结点的个数是否相同。
所以分为以下几步：
- 根据先序建立一棵树，用链表表示
- 判断根结点（题目所给先序的第一个点即根结点）是否是黑色【v[0] < 0】
- 根据建立的树，从根结点开始遍历，如果当前结点是红色，判断它的孩子节点是否为黑色，递归返回结果【jde1函数】
- 从根节点开始，递归遍历，检查每个结点的左子树的高度和右子树的高度（这里的高度指黑色结点的个数），比较左右孩子高度是否相等，递归返回结果【jde2函数】
注意：维基百科定义：红黑树（英语：Red–black tree）是一种自平衡二叉查找树。AVL树：在计算机科学中，AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。所以说红黑树不是一种AVL树，红黑树相对于AVL树来说，牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树。而我根据先序遍历直接建树后判断了是否AVL平衡，把判断是否平衡的那段代码注释掉就AC了～
AC 代码
usingnamespacestd; typedeflonglongll; structnode{ intd; node*left, *right; }; vector<int>v; node*insertRBT(node*rt, intval) { if(rt==NULL) { rt=newnode(); rt->d=val; rt->left=rt->right=NULL; } elseif(abs(rt->d)>=abs(val)) rt->left=insertRBT(rt->left,val); elsert->right=insertRBT(rt->right,val); returnrt; } intgetNum(node*rt) { if(rt==NULL) return0; intl=getNum(rt->left), r=getNum(rt->right); returnrt->d>0?max(l,r)+1 : max(l,r); } intjde1(node*rt) // 判断结点为red时，孩子是否为black{ if(rt==NULL) return1; if(rt->d<0) { if(rt->left!=NULL&&rt->left->d<0) return0; if(rt->right!=NULL&&rt->right->d<0) return0; } returnjde1(rt->left) &&jde1(rt->right); } intjde2(node*rt) // 判断黑结点数是否相等{ if(rt==NULL) return1; intl=getNum(rt->left), r=getNum(rt->right); if(l!=r) return0; returnjde2(rt->left) &&jde2(rt->right); } intmain() { intT; scanf("%d",&T); while(T--) { intn; scanf("%d",&n); node*tree=NULL; v.resize(n); for(inti=0;i<n;i++) { scanf("%d",&v[i]); tree=insertRBT(tree,v[i]); } if(v[0]<0||!jde1(tree) ||!jde2(tree)) puts("No"); elseputs("Yes"); } return0; }
