题目粗心：

给定K给测试用例，每一个测试用例给定一个N个结点的二叉搜寻树的前序序列，要求判断该二叉树是否是红黑树。

算法思路：

首先应用isRed记录所有的红色结点，这样在建树的时候就能够应用负数来建树。而后再依据先序序列建设二叉搜寻树(不须要中序),而后再应用先序遍历判断该数是否是红黑树即可。

建树过程：

每一次递归拜访首先建设根节点并初始化数据，而后找到第一个大于根节点的地位k，这样[preL+1,k-1]为左子树 ，[k,preR]为右子树，别离递归建树就好。

Node* createTree(int preL,int preR){    if(preL>preR) return nullptr;    Node *root = new Node;    root->data = pre[preL];    // 找到第一个大于根节点的地位k    int k;    for(k=preL+1;k<=preR;++k){        if(pre[k]>root->data) break;    }     // [preL+1,k-1]为左子树    root->left =  createTree(preL+1,k-1);    // [k,preR]为右子树    root->right = createTree(k,preR);    return root;}
先序遍历判断过程：

如果root==nullptr，阐明达到叶子结点，将以后门路彩色结点数目countBlack增加进set cntBlack中，而后判断汇合大小是否为1，如果不是阐明不是红黑树。如果不是叶子结点，就拜访该结点，如果是彩色结点，就自增countBlack，如果是红色结点，就判断其存在的孩子是否也是红色结点，如果是就阐明不是红黑树，并返回，否则就递归拜访左子树和右子树。

unordered_set<int> cntBlack;// 记录每一条门路的彩色结点个数void DFS(Node *root,int countBlack,bool &flag){    if(root==nullptr){        // 达到叶子结点         cntBlack.insert(countBlack);        if(cntBlack.size()!=1){            // 呈现不同门路彩色结点不同的状况             flag = false;        }        return;    }    // 以后结点为黑结点     if(!isRed[root->data]){        ++countBlack;    }else {        // 以后结点为红结点        if((root->left!=nullptr&&isRed[root->left->data])||(root->right!=nullptr&&isRed[root->right->data])) {            // 孩子结点也为红色             flag = false;            return;        }    }    DFS(root->left,countBlack,flag);    DFS(root->right,countBlack,flag);}

在建树之前，先判断根节点是否是彩色结点，如果是再建树，能够缩小工夫老本。

留神点：

  • 1、这里须要对于第三条须要顺便阐明一下，叶子结点为空是不是黑的不重要，重要的是肯定得搜寻到空再判断以后门路的彩色结点数目是否统一，否则会呈现判断不齐全，因为从根节点到NULL和到非空叶子结点的门路不齐全一样(前者蕴含后者)，本人入手将NULL补全，画进去就晓得了。
  • 2、对于测试点3呈现的段谬误，个别是2个起因，第一个是开拓的数组太小，最小为3225。第二是建树的时候呈现内存透露，比方没有写return;，也有可能是采纳了不失当的建树形式(我间接采纳前序和中序建树就呈现段谬误，改为前序建树就好了)。
  • 3、每一次查问都得初始化全局变量。

提交后果：

AC代码：

#include<cstdio>#include<vector>#include<cstring>#include<unordered_set>using namespace std;struct Node{    int data;    Node *left;    Node *right;};const int maxn = 3225;// 通过测试，最小为3225，否则测试点3段谬误 bool isRed[maxn];// 记录结点是否是红色的 int pre[maxn];// 前驱序列 unordered_set<int> cntBlack;// 记录每一条门路的彩色结点个数 Node* createTree(int preL,int preR){    if(preL>preR) return nullptr;    Node *root = new Node;    root->data = pre[preL];    // 找到第一个大于根节点的地位k    int k;    for(k=preL+1;k<=preR;++k){        if(pre[k]>root->data) break;    }     // [preL+1,k-1]为左子树    root->left =  createTree(preL+1,k-1);    // [k,preR]为右子树    root->right = createTree(k,preR);    return root;}void DFS(Node *root,int countBlack,bool &flag){    if(root==nullptr){        // 达到叶子结点         cntBlack.insert(countBlack);        if(cntBlack.size()!=1){            // 呈现不同门路彩色结点不同的状况             flag = false;        }        return;    }    // 以后结点为黑结点     if(!isRed[root->data]){        ++countBlack;    }else {        // 以后结点为红结点        if((root->left!=nullptr&&isRed[root->left->data])||(root->right!=nullptr&&isRed[root->right->data])) {            // 孩子结点也为红色             flag = false;            return;        }    }    DFS(root->left,countBlack,flag);    DFS(root->right,countBlack,flag);}int main(){    int K,N;    scanf("%d",&K);    for(int i=0;i<K;++i){        memset(isRed,0,sizeof(isRed));        cntBlack.clear();        scanf("%d",&N);        bool isRedBlackTree = true;        for(int j=0;j<N;++j){            scanf("%d",&pre[j]);            if(pre[j]<0){                pre[j] = -pre[j];                isRed[pre[j]] = true;            }        }        // 根节点是红色结点肯定不是红黑树         if(isRed[pre[0]]) {            isRedBlackTree = false;            printf("No\n");        }else{            // 依据前序遍历构建二叉搜寻树             Node *root = createTree(0,N-1);             // 先序遍历判断以后树是否是红黑树             DFS(root,0,isRedBlackTree);            if(isRedBlackTree){                printf("Yes\n");            }else{                printf("No\n");            }        }    }    return 0;}