【題目描述】
數據結構中有一類平衡的二叉搜索樹，稱為紅黑樹。
它具有以下 5 個屬性：
（1）節點是紅色或黑色。
（2）根節點是黑色。
（3）所有葉子都是黑色。（葉子是 NULL節點）
（4）每個紅色節點的兩個子節點都是黑色。
（5）從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。
例如，下列三張圖中，左圖中的二叉樹是紅黑樹，其餘兩圖中的二叉樹不是紅黑樹。

3、如何判斷一棵樹是否是紅黑樹？_weixin_ci




現在，對於每個給定的二叉搜索樹，請你判斷它是否是合法的紅黑樹。
注意：給定的前序遍歷序列可能不合法，即無法構建出合法二叉搜索樹。

【輸入格式】
第一行包含整數 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：中序遍歷右端點位置。

3、如何判斷一棵樹是否是紅黑樹？_weixin_紅黑樹_02



【算法代碼】 

#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 nodes
        int 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 17

out:
Yes
No
No
*/