A1135 Is It A Red-Black Tree (30分)(红黑树)

一、技术总结

1. 首先说明一下，这一题只是简单的判断是否为红黑树，并没有详细的用到红黑树中的插入、删除等复杂情况。如果想学习可以参考这篇博客：https://www.jianshu.com/p/e136ec79235c
2. 它是在搜索树以及平衡二叉树上发展而来的，但是又不完全是平衡二叉树，因为红黑树对高度差没有严格要求最多相差一。
3. 红黑树的性质说明一下：

• 每个结点要么是红色要么是黑色
• 根结点是黑色
• 每个叶子结点是黑色结点（NIL）
• 红色结点的两个子结点一定是黑色结点
• 任意一结点到每个叶子结点的路径都包含数量相同的黑结点

4. 回归到这一题，我们知道题目给出的是先序遍历，然后我们可以根据先序遍历进行红黑树的创建，本质这里就是创建搜索树（BST），所以我们编写了一个build函数。
5. 然后我们还需要判断每个红色结点的子结点是否还是红色结点，如果出现则不是红黑树，这里我们编写judge1函数。主要的点四在于判断没有左右子树的值是否小于0。
6. 在一个我们判断每一条到叶子结点的路径上，黑色结点的数量是否相等，如果相等这里是如何判断呢，我们首先使用一个getNum函数用于得出每个结点在经过当前结点下子树后黑色结点的数量。；然后再编写judge2函数，判断左右子树在所有路径下黑色结点数是否相等，如果不相等，那么就不是红黑树。
7. 最后就是输出输出，根据题目来即可。

二、参考代码

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
vector<int> arr;
struct node{
	int val;
	node *L, *R;
};
node* build(node *root, int v){
	if(root == NULL){
		root = new node;
		root->val = v;
		root->L = root->R = NULL;
	}else if(abs(v) <= abs(root->val)){
		root->L = build(root->L, v);
	}else{
		root->R = build(root->R, v);
	}
	return root;
}
bool judge1(node* root){
	if(root == NULL) return true;
	if(root->val < 0){
		if(root->L != NULL && root->L->val < 0) return false;
		if(root->R != NULL && root->R->val < 0) return false;
	}
	return judge1(root->L) && judge1(root->R);
}
int getNum(node* root){
	if(root == NULL) return 0;
	int L = getNum(root->L);
	int R = getNum(root->R);
	return root->val > 0 ? max(L, R) + 1 : max(L, R); 
}
bool judge2(node* root){
	if(root == NULL) return true;
	int L = getNum(root->L);
	int R = getNum(root->R);
	if(L != R) return false;
	return judge2(root->L) && judge2(root->R);
}
int main(){
	int k, n;
	scanf("%d", &k);
	for(int i = 0; i < k; i++){
		scanf("%d", &n);
		arr.resize(n);
		node* root = NULL;
		for(int j = 0; j < n; j++){
			scanf("%d", &arr[j]);
			root = build(root, arr[j]);
		}
		if(arr[0] < 0 || judge1(root) == false || judge2(root) == false){
			printf("No
");
		}else{
			printf("Yes
");
		}
	}
	return 0;
}