正文
A1135 | 红黑树判断：审题、根据“先序遍历”和“BST树”的条件生成后序遍历、递归判断
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
对A1135这题有心里阴影了，今天终于拿下AC。学习自柳神博客：https://www.liuchuo.net/archives/4099
首先读题很关键：
There is a kind of balanced binary search tree named red-black tree in the data structure………………
红黑树首先应该是一棵 BST 树，不然从何谈起维护二分查找结构？
所以第一步就应该根据 先序遍历 以及 BST树 的特性来判断是否是一棵BST树，然后根据这两个条件生成树形链式结构。
柳神博客中给出的方法是生成后序遍历然后判断size是否与先序遍历的长度相等。笔者认为生成一个新的先序遍历然后判断长度也可以。
void getPost(int root,int end){//create a BST by pre order and BST's property
if(root>end) return;
int i=root+,j=end;
while(i<=end && pre[root]>pre[i]) i++;
while(j>=root+ && pre[root]<pre[j]) j--;
if(i!=j+) return;
getPost(root+,j);
getPost(i,end);
post.push_back(pre[root]);
}
以上是生成后序遍历的代码。代码逻辑：
7 2 1 5 4 11 8 14 16
j↑ ↑i
让ｉ－＞遍历［root + 1 , 大于root的数］，ｊ＜－遍历［小于root的数 , ｅｎｄ］
然后二者相互错开，建立新的递归关系。
特殊边界条件：
１
＼
２
＼
３
这个结构符合ＢＳＴ树的定义，先序遍历是 １２３。
第一轮：
１ ２ ３
ｊ ｉ
第二轮：
２ ３
ｊ ｉ
第三轮：
３
ij
然后再谈到递归判断。两个递归判断代码：
int getNum(Node* node){
if(!node) return ;
int l=getNum(node->l);
int r=getNum(node->r);
int m=max(l,r);
if(!node->isR) m++;
return m;
}
bool judge1(Node* node){//every path to leaves have same black
if(!node) return true;
if(getNum(node->l)!=getNum(node->r)) return false;
return judge1(node->l) && judge1(node->r);
}
bool judge2(Node* node){//the node is red , the both leaves is black
if(!node) return true;
if(node->isR){
if(node->l && node->l->isR) return false;
if(node->r && node->r->isR) return false;
}
return judge2(node->l) && judge2(node->r);
}
完整代码：
#include <stdio.h>
#include <memory.h>
#include <math.h>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <map> #define I scanf
#define OL puts
#define O printf
#define F(a,b,c) for(a=b;a<c;a++)
#define FF(a,b) for(a=0;a<b;a++)
#define FG(a,b) for(a=b-1;a>=0;a--)
#define LEN 10000
#define MAX 0x06FFFFFF
#define V vector<int> using namespace std; V post;
V pre;
typedef struct Node{
int d=;
bool isR=true;
struct Node* l=NULL;
struct Node* r=NULL;
Node(int D,int I){
d=D;isR=I;
l=NULL;r=NULL;
}
}Node; Node *root=NULL; void getPost(int root,int end);
Node* bst_insert(Node* p,int d);
bool judge1(Node* node);
bool judge2(Node* node); int main() {
freopen("d:/input/A1135/1.txt","r",stdin);
int N,M,i;
scanf("%d",&N);
while(N-->){
scanf("%d",&M);
pre.resize(M);
post.clear();
root=NULL;
FF(i,M){
int t;
scanf("%d",&t);
pre[i]=abs(t);
root=bst_insert(root,t);
}
getPost(,M-);
if(post.size()!=M){
OL("No");continue;
}
if(root->isR){
OL("No");continue;
}
if(judge1(root) && judge2(root))
OL("Yes");
else OL("No");
}
// OL("OK");
return ;
} void getPost(int root,int end){//create a BST by pre order and BST's property
if(root>end) return;
int i=root+,j=end;
while(i<=end && pre[root]>pre[i]) i++;
while(j>=root+ && pre[root]<pre[j]) j--;
if(i!=j+) return;
getPost(root+,j);
getPost(i,end);
post.push_back(pre[root]);
} Node* bst_insert(Node* p,int d){
Node* node=new Node(abs(d),d<);//if d < 0 , d is red
if(!p){//node is null
return node;
}else{
int v=abs(d);
if(v>p->d){//r
if(p->r){
p->r=bst_insert(p->r,d);
}else{
p->r=node;
}
}else{
if(p->l){
p->l=bst_insert(p->l,d);
}else{
p->l=node;
}
}
}
return p;
} int getNum(Node* node){
if(!node) return ;
int l=getNum(node->l);
int r=getNum(node->r);
int m=max(l,r);
if(!node->isR) m++;
return m;
} bool judge1(Node* node){//every path to leaves have same black
if(!node) return true;
if(getNum(node->l)!=getNum(node->r)) return false;
return judge1(node->l) && judge1(node->r);
} bool judge2(Node* node){//the node is red , the both leaves is black
if(!node) return true;
if(node->isR){
if(node->l && node->l->isR) return false;
if(node->r && node->r->isR) return false;
}
return judge2(node->l) && judge2(node->r);
}
