PAT (Advanced Level) 1135 Is It A Red-Black Tree (30分)
1节点是红色或黑色
2根节点是黑色
3所有NULL节点是黑色
4所有红色节点的子节点是黑色
5从任何一个节点到其每个叶子的所有路径都包含相同数目的黑色节点
因为是递归的对每一个节点的左右子树进行判断，所以理论上左右子树到叶子节点的 路径上的 黑色节点的数量都是一样的。所以不必纠结 Get_Num 中的max。
#include<iostream> #include<cstring> //memset #include<string> #include<cstdio> //scanf #include<string> #include<utility> // pair #include<algorithm> #include<queue> #include<cmath> #include<stack> #include<list> #include<map> #include<unordered_map> #include<unordered_set> #include<set> #include<functional> //less greater using namespace std; #define LL long long int #define ll LL #define INF 0x3f3f3f3f const int maxn = 1e5 + 10; int N; int flag; struct Node { int data; int color; int numed; Node *Left; Node *Right; Node() { data = 0; color = 0; numed = 0; Left = NULL; Right = NULL; } }; Node *rt = new Node(); void insert(Node * rt, int x, int ys) { if (rt->numed == 0) { rt->numed = 1; rt->data = x; rt->color = ys; return; } if (x < rt->data) { if (rt->Left == NULL) rt->Left = new Node(); insert(rt->Left, x, ys); } else { if (rt->Right == NULL) rt->Right = new Node(); insert(rt->Right, x, ys); } } void dfs(Node *rt, int pre) { if (rt == NULL || rt->numed == 0) return; if (pre == -1) { if (rt->color != 1) { flag = 0; return; } } if (rt->Left != NULL) dfs(rt->Left, rt->color); if (rt->Right != NULL) dfs(rt->Right, rt->color); } int Get_Num(Node *rt) { if (rt == NULL || rt->numed == 0) return 0; int L = Get_Num(rt->Left); int R = Get_Num(rt->Right); return rt->color == 1 ? max(L, R) + 1 : max(L, R); } int judge(Node *rt) { if (rt == NULL || rt->numed == 0) return 1; int L = Get_Num(rt->Left); int R = Get_Num(rt->Right); if (L != R) return false; return judge(rt->Left) && judge(rt->Right); } int main() { int T; scanf("%d", &T); while (T--) { delete rt; flag = 1; rt = new Node(); scanf("%d", &N); for (int i = 1; i <= N; i++) { int x; scanf("%d", &x); if (x > 0) insert(rt, x, 1); else insert(rt, abs(x), -1); } if (rt->color != 1) flag = 0; if (flag) dfs(rt, 1); if (flag) flag = judge(rt); if (flag) puts("Yes"); else puts("No"); } return 0; }