本文共 1798 字，大约阅读时间需要 5 分钟。

题目链接：

题目大意：给一棵二叉搜索树的前序遍历，判断它是否为红黑树，是输出Yes，否则输出No。

解题思路：

判断以下几点：

1. 根结点是否为黑色；
2. 如果一个结点是红色，它的孩子节点是否都为黑色；
3. 从任意结点到叶子结点的路径中，黑色结点的个数是否相同。

所以分为以下几步：

1. 根据先序建立一棵树，用链表表示
2. 判断根结点（题目所给先序的第一个点即根结点）是否是黑色【v[0] < 0】
3. 根据建立的树，从根结点开始遍历，如果当前结点是红色，判断它的孩子节点是否为黑色，递归返回结果【jde1函数】
4. 从根节点开始，递归遍历，检查每个结点的左子树的高度和右子树的高度（这里的高度指黑色结点的个数），比较左右孩子高度是否相等，递归返回结果【jde2函数】

注意：维基百科定义：红黑树（英语：Red–black tree）是一种自平衡二叉查找树。AVL树：在计算机科学中，AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。所以说红黑树不是一种AVL树，红黑树相对于AVL树来说，牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树。而我根据先序遍历直接建树后判断了是否AVL平衡，把判断是否平衡的那段代码注释掉就AC了～

AC 代码

#include
   
    #include
    
     #define mem(a,b) memset(a,b,sizeof a)#define ssclr(ss) ss.clear(), ss.str("")#define INF 0x3f3f3f3f#define MOD 1000000007using namespace std;typedef long long ll;struct node{    int d;    node *left, *right;};vector
     
       v;node *insertRBT(node *rt, int val){    if(rt==NULL)    {        rt=new node();        rt->d=val;        rt->left=rt->right=NULL;    }    else if(abs(rt->d)>=abs(val)) rt->left=insertRBT(rt->left,val);    else rt->right=insertRBT(rt->right,val);    return rt;}int getNum(node *rt){    if(rt==NULL) return 0;    int l=getNum(rt->left), r=getNum(rt->right);    return rt->d>0 ? max(l,r)+1 : max(l,r);}int jde1(node *rt) // 判断结点为red时，孩子是否为black{    if(rt==NULL) return 1;    if(rt->d<0)    {        if(rt->left!=NULL && rt->left->d<0) return 0;        if(rt->right!=NULL && rt->right->d<0) return 0;    }    return jde1(rt->left) && jde1(rt->right);}int jde2(node *rt) // 判断黑结点数是否相等{    if(rt==NULL) return 1;    int l=getNum(rt->left), r=getNum(rt->right);    if(l!=r) return 0;    return jde2(rt->left) && jde2(rt->right);}int main(){    int T; scanf("%d",&T);    while(T--)    {        int n;        scanf("%d",&n);        node *tree=NULL;        v.resize(n);        for(int i=0;i
     
    
   

转载地址：https://lux-sun.blog.csdn.net/article/details/82151412 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！