# P1087 [NOIP 2004 普及组] FBI 树

## 题目描述

我们可以把由 0 和 1 组成的字符串分为三类：全 0 串称为 B 串，全 1 串称为 I 串，既含 0 又含 1 的串则称为 F 串。

FBI 树是一种二叉树，它的结点类型也包括 F 结点，B 结点和 I 结点三种。由一个长度为 2^N 的 01 串 S 可以构造出一棵 FBI 树 T，递归的构造方法如下：

1. T的根结点为 R，其类型与串 S 的类型相同；
2. 若串 S 的长度大于 1，将串 S 从中间分开，分为等长的左右子串 S_1 和 S_2；由左子串 S_1 构造 R 的左子树 T_1，由右子串 S_2 构造 R的右子树 T_2。

现在给定一个长度为 $2^N$ 的 01 串，请用上述构造方法构造出一棵 FBI 树，并输出它的后序遍历序列。

## 输入格式

第一行是一个整数 N(0 \le N \le 10)，  

第二行是一个长度为 2^N 的 01 串。

## 输出格式

一个字符串，即 FBI 树的后序遍历序列。

##输入输出样例#1

###输入#1

```
3
10001011
```

###输出#1

```
IBFBBBFIBFIIIFF
```

noip2004普及组第3题

函数 build(l, r)处理子串 s[l..r]：
如果 l == r，根据 s[l]返回 "B"或 "I"。否则，计算中点 mid = (l + r) / 2，递归得到左子树后序 left_str和右子树后序 right_str。
判断当前子串类型：
如果全 0→ "B"。如果全 1→ "I"，否则 → "F"。返回 left_str + right_str + ，当前节点类型判断全 0 / 全 1​，可以在递归时传入子串范围，检查该范围内是否所有字符相同且为 '0'或 '1'。
代码如下：
#include <iostream>
#include <string>
using namespace std;

string s;
int n;

// 判断子串 s[l..r] 是否全为 ch
bool allChar(int l, int r, char ch) {
    for (int i = l; i <= r; i++) {
        if (s[i] != ch) return false;
    }
    return true;
}

// 递归构建后序遍历
string build(int l, int r) {
    if (l == r) {
        if (s[l] == '0') return "B";
        else return "I";
    }
    
    int mid = (l + r) / 2;
    string leftStr = build(l, mid);
    string rightStr = build(mid + 1, r);
    
    // 判断当前节点类型
    bool has0 = !allChar(l, r, '1');
    bool has1 = !allChar(l, r, '0');
    
    string nodeType;
    if (!has0 && has1) nodeType = "I";
    else if (has0 && !has1) nodeType = "B";
    else nodeType = "F";
    
    return leftStr + rightStr + nodeType;
}

int main() {
    cin >> n;
    cin >> s;
    int len = 1 << n; // 2^n
    // 确保长度正确
    s = s.substr(0, len);
    cout << build(0, len - 1) << endl;
    return 0;
}