descendant

n . 后裔，子孫；（由過去類似物發(fā)展來的）派生物；（機(jī)器等）后繼型產(chǎn)品

adj. 下降的槐沼；祖?zhèn)鞯?/p>

思路

給一棵二叉搜索樹的前序遍歷，判斷它是否為紅黑樹捌治，是輸出Yes岗钩，否則輸出No。

首先是建樹問題：紅黑樹是二叉搜索樹具滴，所以給出前序遍歷，中序遍歷也可以知道（從小到大排序就是中序遍歷)师倔，負(fù)號(hào)不代表大小

然后根據(jù)紅黑樹Red-Black Tree特點(diǎn)進(jìn)行判斷

1. 根結(jié)點(diǎn)是否為黑色

   判斷根結(jié)點(diǎn)（題目所給先序的第1個(gè)點(diǎn)即根結(jié)點(diǎn)）是否是黑色

2. 將NULL看成1個(gè)葉子節(jié)點(diǎn)构韵，為黑色

3. 如果1個(gè)結(jié)點(diǎn)是紅色，它的孩子節(jié)點(diǎn)是否都為黑色

   根據(jù)建立的樹趋艘，從根結(jié)點(diǎn)開始遍歷疲恢，如果當(dāng)前結(jié)點(diǎn)是紅色，判斷它的孩子節(jié)點(diǎn)是否為黑色瓷胧，遞歸返回結(jié)果

4. 從任意結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑中显拳，黑色結(jié)點(diǎn)的個(gè)數(shù)是否相同

   求該節(jié)點(diǎn)的高度值，這里的高度是只計(jì)算黑節(jié)點(diǎn)在內(nèi)的高度搓萧，然后比較左右兩個(gè)子樹的包含的黑色高度是否相同杂数，如果相同則滿足條件，否則不滿足瘸洛。

代碼

#include <bits/stdc++.h>
using namespace std;

struct node{
    int data;
    node* lchild;
    node* rchild;
    node(int d): data(d), lchild(NULL), rchild(NULL) {}
};

vector<int> prenum;
vector<int> innum;
int flag = 0;

node* create(int prea, int preb, int ina, int inb) {
    if (prea > preb) return NULL;
    int ro = prenum[prea];
    node* root = new node(ro);
    int i;
    for (i = ina; i <= inb; i++) {
        if (innum[i] == abs(ro)) break;
    }
    int numleft = i - ina;
    root->lchild = create(prea + 1, prea + numleft, ina, ina + numleft - 1);
    root->rchild = create(prea + numleft + 1, preb, ina + numleft + 1, inb);
    return root;
}

void dfs(node* root) {
    if (root == NULL) return;
    if (root->data < 0) {
        if (root->lchild != NULL && root->lchild->data < 0) {
            flag = 1;
        }
        if (root->rchild != NULL && root->rchild->data < 0) {
            flag = 1;
        }
    }
    dfs(root->lchild);
    dfs(root->rchild);
}

int getNum(node *root) {
    if (root == NULL) return 0;
    int l = getNum(root->lchild);
    int r = getNum(root->rchild);
    return root->data > 0 ? max(l,r)+1 : max(l,r); // 只記錄黑節(jié)點(diǎn) 
}
 
bool judge2(node *root) {
    if (root == NULL) return true;
    int l = getNum(root->lchild);
    int r = getNum(root->rchild);
    if (l != r) return false;
    return judge2(root->lchild) && judge2(root->rchild);
}

int main() {
    int n;
    cin>>n;
    while (n--) {
        int num;
        flag = 0;
        cin>>num; 
        prenum.resize(num + 1);
        innum.resize(num + 1);
        for (int i = 0; i < num; i++) {
            cin>>prenum[i];
            innum[i] = abs(prenum[i]);
        }
        sort(innum.begin(), innum.begin() + num);
        node* root = NULL;
        root = create(0, num - 1, 0, num - 1);
        if (prenum[0] < 0) flag = 1;
        dfs(root);
        if (!judge2(root)) flag = 1;
        if (flag == 1) cout<<"No"<<endl;
        else cout<<"Yes"<<endl;
    }
}