1135. Is It A Red-Black Tree.md

pat 甲级 1135 Is It A Red-Black Tree

题意概述

红黑树是一种平衡二叉查找树，它满足以下要求：

1. 每个节点都是红色或黑色。
2. 根是黑色的。
3. 每个叶子（NULL）都是黑色的。
4. 如果一个节点是红色的，那么它的两个孩子都是黑色的。
5. 对于每个节点，从节点到后代叶子结点的所有简单路径包含相同数量的黑色节点。

给出二叉查找树的先根序列，判断该树是否是红黑树。

输入输出格式

输入第一行给出一个正整数 K，它是用例总数。对于每个样例，第一行给出一个正整数 N，即二叉树中节点的总数。第二行给出了树的先根遍历序列。虽然树中的所有键都是正整数，但我们使用负号表示红色节点。一行中的所有数字都用空格分隔。

对于每个测试用例，如果给定的树是一棵红黑树，则打印Yes，如果不是，则打印No。

数据规模

$$K<=30,N<=30$$

算法设计

根据给的红黑树的性质可知主要需要判断 2、4、5 三条性质。由于给出的树一定是一棵二叉查找树，我们可以根据先根序列重建这棵树，在重建树之后，性质 2 和性质 4 很容易判断。我们着重思考一下如何判断性质 5。我们可以进行一次后根遍历，先计算每个结点的左孩子结点和右孩子结点到叶节点的黑色结点个数lnum和rnum，如果lnum!=rnum，即不满足性质 5；如果lnum==rnum，返回lnum+(根结点是黑色结点?1:0)。

我们可以把重建树和后根遍历结合在一起，在不需真正重建树的基础上验证这些性质，具体实现可见代码。

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
gg dfs(vector<gg>& pre, gg left, gg right, bool& ans) {
    if (left > right) {
        return 0;
    }
    gg i = find_if(pre.begin() + left, pre.begin() + right + 1,
                   [&pre, left](gg a) { return abs(a) > abs(pre[left]); }) -
           pre.begin();
    if (pre[left] < 0 and ((left + 1 <= right and pre[left + 1] < 0) or
                           (i <= right and pre[i] < 0))) {
        ans = false;
    }
    gg lnum = dfs(pre, left + 1, i - 1, ans), rnum = dfs(pre, i, right, ans);
    if (lnum != rnum) {
        ans = false;
    }
    return lnum + (pre[left] > 0 ? 1 : 0);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    gg ki, ni;
    cin >> ki;
    while (ki--) {
        cin >> ni;
        vector<gg> pre(ni);
        bool ans = true;
        for (gg& i : pre) {
            cin >> i;
        }
        dfs(pre, 0, ni - 1, ans);
        cout << ((ans and pre[0] > 0) ? "Yes" : "No") << "\n";
    }
    return 0;
}