递归处理每个二分区间，先输出左右子树结果，再用区间内 0/1 的分布判定当前结点类型。
OJ: luogu
题目 ID: P1087
难度:普及-
标签:递归二叉树分治
日期: 2026-06-19 20:00
题意
给出一个长度为 2^N 的 01 串。每次把当前串的类型判成：
- 全
0是B - 全
1是I - 同时含
0和1是F
然后把它从中间分成左右两半，递归构造左右子树。题目要求输出这棵 FBI 树的后序遍历。
思路
最直接的办法是按题意真的把整棵树建出来，再做一次后序遍历。
先看一个可以直接验证想法的朴素解：
cpp
#include <bits/stdc++.h>
using namespace std;
static string bits;
struct Node {
char type;
Node *left;
Node *right;
Node(char type_) : type(type_), left(nullptr), right(nullptr) {}
};
// 直接扫描区间，按定义判断这个子串对应的结点类型。
char segment_type(int l, int r) {
bool has_zero = false;
bool has_one = false;
for (int i = l; i <= r; ++i) {
if (bits[i - 1] == '0') {
has_zero = true;
} else {
has_one = true;
}
}
if (has_zero && has_one) {
return 'F';
}
if (has_zero) {
return 'B';
}
return 'I';
}
// 按题意显式建出整棵树，更适合教学理解与小数据对拍。
Node* build(int l, int r) {
Node *node = new Node(segment_type(l, r));
if (l == r) {
return node;
}
int mid = (l + r) >> 1;
node->left = build(l, mid);
node->right = build(mid + 1, r);
return node;
}
void postorder(Node *node) {
if (node == nullptr) {
return;
}
postorder(node->left);
postorder(node->right);
cout << node->type;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n >> bits;
int m = 1 << n;
Node *root = build(1, m);
postorder(root);
cout << '\n';
return 0;
}brute.cpp 对每个区间重新扫描一遍，判断它是 B、I 还是 F，然后显式建树。这个版本很直观，适合帮助理解和对拍。
正式解可以再进一步：我们其实不需要真的建树，只需要知道每个区间的类型，并按“左、右、根”的顺序输出。
样例树
这张图展示样例串 10001011 递归切分后得到的 FBI 树：
graph TD A["10001011 / F"] --> B["1000 / F"] A --> C["1011 / F"] B --> D["10 / F"] B --> E["00 / B"] C --> F["10 / F"] C --> G["11 / I"] D --> H["1 / I"] D --> I["0 / B"] E --> J["0 / B"] E --> K["0 / B"] F --> L["1 / I"] F --> M["0 / B"] G --> N["1 / I"] G --> O["1 / I"]
从图里可以看到，每个结点都只对应原串中的一个连续区间，而且左右儿子就是这段区间的左右两半。 所以整棵树的结构早就由“不断二分”确定了，真正需要判断的只剩下每个区间的类型。 后序遍历也很直接：先输出左子树，再输出右子树，最后输出当前区间类型。
为了快速判断区间类型，可以先做一个前缀和数组，统计前 i 个字符里有多少个 1。这样就能在 1 的数量：
- 数量为
0，当前结点是B - 数量等于区间长度，当前结点是
I - 否则当前结点是
F
于是写一个 solve(l, r)：
- 若区间长度为
1，直接输出类型 - 递归处理左半段
- 递归处理右半段
- 最后输出整个区间的类型
这样就正好按后序遍历输出答案。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
static int n;
static string bits;
static vector<int> prefix_one;
// 用前缀和 O(1) 判断当前区间是 B、I 还是 F。
char segment_type(int l, int r) {
int ones = prefix_one[r] - prefix_one[l - 1];
int len = r - l + 1;
if (ones == 0) {
return 'B';
}
if (ones == len) {
return 'I';
}
return 'F';
}
// 后序遍历顺序是左、右、根，因此递归完左右区间后再输出当前类型。
void solve(int l, int r) {
if (l == r) {
cout << segment_type(l, r);
return;
}
int mid = (l + r) >> 1;
solve(l, mid);
solve(mid + 1, r);
cout << segment_type(l, r);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> bits;
int m = 1 << n;
prefix_one.assign(m + 1, 0);
for (int i = 1; i <= m; ++i) {
prefix_one[i] = prefix_one[i - 1] + (bits[i - 1] == '1');
}
solve(1, m);
cout << '\n';
return 0;
}复杂度
设原串长度为 m = 2^N。
前缀和预处理是
总结
这题的关键不是“怎么建树”，而是看出树的结构已经由不断二分固定好了。剩下只要按后序递归顺序处理每个区间，并判断它属于 B、I 还是 F 就行。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
