共计 2901 个字符，预计需要花费 8 分钟才能阅读完成。
题目粗心：
给定 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] = true;
}
}
// 根节点是红色结点肯定不是红黑树
if(isRed]) {
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;
}
