FBI树

形式化题目

给定长度为 $2^N$ 的 01 串（ $0\leqslant N\leqslant 10$ ）。按规则构造 FBI 树：根结点类型由整串决定（全 0 为 B，全 1 为 I，否则为 F）；长度大于 1 时从中间分成左右等长子串，分别递归构造左右子树。输出该树的后序遍历序列。

输入：第一行整数 $N$ ，第二行 01 串。
输出：一行字符串，即后序遍历序列。

样例输入：3 / 10001011，样例输出：IBFBBBFIBFIIIFF。

解法总览

两种解法共用同一条分治规则：一段 01 子串就是一棵 FBI 子树，根类型看整段含 0 还是 1，串长大于 1 就从中间对半切。差别只在「后序序列是直接拼出来，还是先把树存下来再走一遍」。

	解法一：子串递归直接拼（原实现）	解法二：先建树再后序（正式主解）
做法	递归返回左右两半的后序串，拼上根类型	`new_node()` 建出 `Node{type, lch, rch}`，再 `postorder(root)` 收集
中间结构	递归返回的临时字符串（Python 用 `@cache` 按子串去重）	结点表 O(L)，可复用
时间	每个结点扫一遍自己的子串定类型，O(L log L)	同左，另有 O(L) 的建树与遍历
代码	`direct.py` / `direct.cpp`	`main.py` / `main.cpp`

正式主解是 main.py / main.cpp。

解法一：子串递归直接拼

思路

子串区间与 FBI 子树一一对应。递归处理左右两半，返回后序序列，再拼接根结点类型即可。长度 1 时直接返回该字符对应的 B/I。

代码

Python 版（原实现，@cache 保证同一子串只算一次）：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 07:15
# update_at: 2026-10-12 15:05
# direct.py：原方法——区间/子串递归直接产出，不显式建结点树（对比新方法见 main.py）。

# FBI 树：子串区间递归，直接算出后序序列，不显式建结点。
# 一段 01 串 bits 就对应一棵 FBI 子树：全 0 为 B，全 1 为 I，既有 0 又有 1 为 F，
# 串长大于 1 时从中间切成等长两半，后序 = 左半 + 右半 + 根。
# 如何使用：
# 1. read_input()   # 读入 N 和 01 串 s
# 2. postorder(s)   # 返回串 s 构造出的 FBI 树的后序遍历序列
# 3. solve()        # 装配：读入 -> 递归 -> 输出

import sys
from functools import cache

s = "" # 输入的 01 串，串长 2^N


def read_input() -> None:
    """读入 N 和 01 串。"""
    global s
    data = sys.stdin.buffer.read().decode().split()
    s = data[1] if int(data[0]) else ""  # N == 0 时按空串处理


def node_kind(bits: str) -> str:
    """判断一段 01 串对应的 FBI 结点类型：全 0 为 B，全 1 为 I，否则为 F。"""
    return "B" if "1" not in bits else "I" if "0" not in bits else "F"


@cache
def postorder(bits: str) -> str:
    """返回 bits 所构造 FBI 树的后序遍历序列。"""
    mid = len(bits) // 2
    # 长度大于 1 时先递归左右子树，再拼上根；长度为 1 时直接返回自身类型。
    return postorder(bits[:mid]) + postorder(bits[mid:]) + node_kind(bits) if mid else node_kind(bits)


def solve() -> None:
    read_input()
    print(postorder(s))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 12:07
 * update_at: 2026-10-05 12:07
 */
// direct.cpp：原方法——子串递归直接拼出后序序列，不显式建结点树（对比新方法见 main.cpp）。

#include <iostream>
#include <string>
using namespace std;

typedef long long ll;

const int MAXN = 1 << 10; // N <= 10，最大长度 1024

char s[MAXN + 5]; // 输入的 01 串

// 判断子串 s[l..r-1] 的结点类型：全 0 为 B，全 1 为 I，否则为 F
char node_kind(int l, int r) {
    bool has0 = false, has1 = false;
    for (int i = l; i < r; ++i) {
        if (s[i] == '0') has0 = true;
        else has1 = true;
        if (has0 && has1) return 'F';
    }
    if (has0) return 'B';
    return 'I';
}

// 递归返回子串 s[l..r-1] 对应 FBI 树的后序遍历序列
string postorder(int l, int r) {
    if (r - l == 1) {
        return string(1, node_kind(l, r));
    }
    int mid = (l + r) >> 1;
    return postorder(l, mid) + postorder(mid, r) + node_kind(l, r);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n >> s;
    int len = 1 << n; // 2^N
    cout << postorder(0, len) << '\n';
    return 0;
}

复杂度

时间：每个结点都要扫自己的子串判断类型，所有子串长度之和为 O(L log L)（树是完全二叉的，每层共 L 个字符，共 log L + 1 层）。
空间：递归栈 O(log L)，加上返回的字符串与缓存 O(L log L)。

解法二：先建树再后序

思路

规则完全一样，区别在于先把树存下来：build(l, r) 对子串开一个结点、算好类型，串长大于 1 时从 mid = (l + r) / 2 切开，把左右孩子接上；建完再从根做一遍 postorder(u)，左、右、根依次收集类型。

结点的类型、左儿子、右儿子收进同一个 Node，编号即下标（静态数组 + node_cnt 动态开点）。树一旦存下来，后序只是三行递归；要改成先序、中序或统计结点数，也不必再碰原串。

代码

Python 版：