【题目来源】
https://www.acwing.com/problem/content/1630/
【题目描述】
数据结构中有一类平衡的二叉搜索树，称为红黑树。
它具有以下 5 个属性：
（1）节点是红色或黑色。
（2）根节点是黑色。
（3）所有叶子都是黑色。（叶子是 NULL节点）
（4）每个红色节点的两个子节点都是黑色。
（5）从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
例如，下列三张图中，左图中的二叉树是红黑树，其余两图中的二叉树不是红黑树。
现在，对于每个给定的二叉搜索树，请你判断它是否是合法的红黑树。
注意：给定的前序遍历序列可能不合法，即无法构建出合法二叉搜索树。
【输入格式】
第一行包含整数 K，表示共有 K 组测试数据。
每组测试数据，第一行包含整数 N，表示二叉搜索树的节点数量。
第二行给出了这个二叉搜索树的前序遍历。
注意，虽然所有节点的权值都为正，但是我们使用负号表示红色节点。
各节点权值互不相同。
输入样例与题目中三个图例相对应。
【输出格式】
对于每组数据，如果是合法红黑树则输出一行 Yes，否则输出一行 No。
【输入样例】
3
9
7 -2 1 5 -4 -11 8 14 -15
9
11 -2 1 -7 5 -4 8 14 -15
8
10 -7 5 -6 8 15 -11 17
【输出样例】
Yes
No
No
【数据范围】
1≤K≤30，
1≤N≤30
【算法分析】
● 红黑树性质助记口诀：左根右、根叶黑、不红红、黑路同。
● 利用先序、中序遍历序列求后序遍历序列的示意图，以及计算图中 x、y 值的过程，如下所示。其中：
pl：先序遍历左端点位置，pr：先序遍历右端点位置。
il：中序遍历左端点位置，ir：中序遍历右端点位置。
【算法代码】
#include<bits/stdc++.h>
using namespace std;unordered_map<int, int> pos;
const int maxn=35;
int pre[maxn],in[maxn];
bool ans;int build(int il,int ir,int pl,int pr,int& sum) {int rt=pre[pl];int k=pos[abs(rt)];if(k<il || k>ir) {ans=false;return 0;}int le=0,ri=0,ls=0,rs=0;if(il<k) le=build(il,k-1,pl+1,pl+1+k-1-il,ls);if(k<ir) ri=build(k+1,ir,pl+1+k-1-il+1,pr,rs);if(ls!=rs) ans=false;sum=ls;if(rt<0) {if(le<0 || ri<0) ans=false;} else sum++;return rt;
}int main() {int T;cin>>T;while(T--) {int n;cin>>n;for(int i=0; i<n; i++) {cin>>pre[i];in[i]=abs(pre[i]);}sort(in,in+n);pos.clear();for(int i=0; i<n; i++) pos[in[i]]=i;ans=true;int sum; //number of black nodesint rt=build(0,n-1,0,n-1,sum);if(rt<0) ans=false;if(ans) cout<<"Yes\n";else cout<<"No\n";}return 0;
}/*
in:
3
9
7 -2 1 5 -4 -11 8 14 -15
9
11 -2 1 -7 5 -4 8 14 -15
8
10 -7 5 -6 8 15 -11 17out:
Yes
No
No
*/
【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/119108633
https://blog.csdn.net/hnjzsyjyj/article/details/145047068
https://www.cnblogs.com/xjtfate/p/16603241.html
https://www.acwing.com/solution/content/145808/
https://blog.csdn.net/hnjzsyjyj/article/details/155001635