洛谷-P1087 [NOIP 2004 普及组] FBI 树 题解

题目链接：https://www.luogu.com.cn/problem/P1087

题目大意

给定一个长度为 2^N 的 01 字符串，按照如下规则构建一棵 FBI 树：

• 如果字符串全是 0，称为 B 串，对应节点类型为 'B'
• 如果字符串全是 1，称为 I 串，对应节点类型为 'I'
• 否则（既有 0 又有 1），称为 F 串，对应节点类型为 'F'

构建方式是递归的：

• 根节点表示整个字符串
• 若字符串长度大于 1，则从中间切开成两个等长子串，分别构造左右子树

最后要求输出这棵 FBI 树的 后序遍历序列。

解题思路

1. 递归建树 + 后序遍历

题目已经给出了明确的递归结构，我们可以直接模拟这个过程：

• 对于当前区间 [l, r]，判断该子串属于 B、I 还是 F
• 如果长度为 1（即 l == r），直接设为 'B' 或 'I'
• 否则，递归处理左右两半，再根据左右子树的类型决定当前节点类型
• 最后进行后序遍历（左 → 右 → 根）

2. 节点类型的判定逻辑

• 若左右子树都是 'B'，说明整段都是 0，当前节点为 'B'
• 若左右子树都是 'I'，说明整段都是 1，当前节点为 'I'
• 其他情况（混合或其中一个是 'F'），当前节点为 'F'

注意：不需要每次都扫描整个子串来判断是否全 0 或全 1，因为递归过程中子问题已经帮我们判断好了。

代码实现解析

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

struct Node {
    char val;
    Node* left, * right;
};

string str;
int n;

// 递归构建 FBI 树
void process(Node* cur, int l, int r)
{
    if (l == r) // 叶子节点
    {
        cur->left = nullptr;
        cur->right = nullptr;
        if (str[l] == '0')
            cur->val = 'B';
        else
            cur->val = 'I';
        return;
    }

    int mid = (l + r) / 2;
    cur->left = new Node();
    cur->right = new Node();

    // 递归构建左右子树
    process(cur->left, l, mid);
    process(cur->right, mid + 1, r);

    // 根据左右子树类型确定当前节点类型
    if (cur->left->val == 'B' && cur->right->val == 'B')
        cur->val = 'B';
    else if (cur->left->val == 'I' && cur->right->val == 'I')
        cur->val = 'I';
    else
        cur->val = 'F';
}

// 后序遍历
void Order(Node* cur)
{
    if (!cur) return;
    Order(cur->left);
    Order(cur->right);
    cout << cur->val;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n;
    cin >> str;

    Node* root = new Node();
    process(root, 0, str.size() - 1);
    Order(root);
    
    return 0;
}

复杂度分析

• 时间复杂度：每个字符在每一层被访问一次，总共有 N+1 层（因为长度是 2^N），所以总时间复杂度为 O(N * 2^N)，也可以理解为每个节点只被处理一次，共 2^（N+1）- 1 个节点，即 O(2^N)。
• 空间复杂度：递归栈深度为 N+1，加上建树所用空间，也是 O(2^N)。

总结

本题考察的是对递归建树和树的遍历的理解。关键在于：

• 利用子问题的结果判断当前节点类型，避免重复扫描字符串
• 正确实现后序遍历
• 注意边界条件（如 N=0 时字符串长度为 1）

通过递归分治的方式，可以高效地构建 FBI 树并完成遍历。