P1087 FBI树

calendar May 10, 2026 · 5 分钟阅读 · 递归 二叉树  ·
分享到: linkedin copy

文章目录

题目信息

字段 内容
题号 P1087
难度 普及-
知识点 递归、二叉树、后序遍历

题目描述

将由 "0" 和 "1" 组成的字符串分为三类：

  • B 串：全为 "0" 的串
  • I 串：全为 "1" 的串
  • F 串：既含 "0" 又含 "1" 的串

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

  1. T 的根结点为 R，其类型与串 S 的类型相同
  2. 若串 S 的长度大于 1，将串 S 从中间分开，分为等长的左右子串 S1 和 S2
    • 由左子串 S1 构造 R 的左子树 T1
    • 由右子串 S2 构造 R 的右子树 T2

给定一个长度为 2^N 的 "01" 串，构造出对应的 FBI 树，并输出其后序遍历序列。

输入格式

  • 第一行：一个整数 N（0 ≤ N ≤ 10）
  • 第二行：一个长度为 2^N 的 "01" 字符串

输出格式

  • 一行字符串，即 FBI 树的后序遍历序列（由 F、B、I 组成）

样例

输入：

3
10001011

输出：

IBFBBBFIBFIIIFF

解题思路

核心思想

这道题考察递归和二叉树后序遍历。

后序遍历的顺序是：左子树 → 右子树 → 根结点

我们可以设计一个递归函数 build(l, r)，处理字符串中 [l, r] 区间：

  1. 递归处理左子树：build(l, mid)
  2. 递归处理右子树：build(mid+1, r)
  3. 输出当前根结点类型：判断 [l, r] 区间内是全 0、全 1 还是混合

为什么这样是正确的？

题目要求后序遍历，所以我们在递归调用完左右子树之后，再输出当前结点的类型。这正是后序遍历的定义。

类型判断

对于区间 [l, r]：

  • 如果全是 '0'，输出 'B'
  • 如果全是 '1'，输出 'I'
  • 否则，输出 'F'

完整代码

C++

#include <bits/stdc++.h>
using namespace std;

int n;
string s;

/**
 * 递归构造 FBI 树并输出后序遍历
 * @param l 区间左端点（从 0 开始）
 * @param r 区间右端点
 */
void build(int l, int r) {
    // 后序遍历：先左，再右，最后根
    if (r > l) {
        int mid = (l + r) / 2;
        build(l, mid);          // 左子树
        build(mid + 1, r);      // 右子树
    }
    
    // 判断当前区间的类型（根结点）
    bool all_zero = true;   // 是否全是 '0'
    bool all_one = true;    // 是否全是 '1'
    
    for (int i = l; i <= r; i++) {
        if (s[i] == '0') {
            all_one = false;
        } else if (s[i] == '1') {
            all_zero = false;
        }
    }
    
    // 输出结点类型
    if (all_one) {
        cout << 'I';
    } else if (all_zero) {
        cout << 'B';
    } else {
        cout << 'F';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> s;
    int len = s.size() - 1;
    
    build(0, len);
    
    cout << '\n';
    return 0;
}

代码说明

你的原代码有一个变量名冲突问题：

int b=1,i=1,f=0;  // ❌ f 与函数名 f 冲突！

这会导致编译错误或逻辑错误。我已修正为：

bool all_zero = true;
bool all_one = true;

关键代码讲解

1. 递归终止条件

if (r > l) {
    int mid = (l + r) / 2;
    build(l, mid);
    build(mid + 1, r);
}

当 r == l 时，区间只有一个字符，不需要再递归。

2. 后序遍历的输出时机

// 递归调用在前面（处理左右子树）
if (r > l) {
    build(l, mid);
    build(mid + 1, r);
}
// 输出在后面（输出根结点）
cout << ...;

这保证了输出顺序是：左 → 右 → 根

3. 类型判断

for (int i = l; i <= r; i++) {
    if (s[i] == '0') all_one = false;
    if (s[i] == '1') all_zero = false;
}

遍历区间内的所有字符，如果两个标志都被置为 false，说明既有 0 又有 1，输出 'F'。

复杂度分析

方法 时间复杂度 空间复杂度
递归 + 遍历判断 O(N × 2^N) O(N)

解释：

  • 字符串长度为 2^N
  • 每个结点都需要遍历其区间判断类型，最坏 O(区间长度)
  • 递归深度为 O(N)

数据范围： N ≤ 10，最大字符串长度为 1024，完全可接受。

易错点

  1. 后序遍历顺序错误：先输出再递归（错），先递归再输出（对）
  2. 变量名冲突：不要使用与函数名相同的变量名
  3. 区间边界错误：mid = (l + r) / 2，右子树从 mid + 1 开始
  4. 字符串索引：题目输入的字符串可能包含换行符，建议使用 cin >> s 直接读入

其他语言解法

Python

'''P1087 FBI树 - Python 解法'''


def build(l: int, r: int, s: str) -> None:
    '''递归构造 FBI 树并输出后序遍历'''
    # 后序遍历：先左，再右，最后根
    if r > l:
        mid = (l + r) // 2
        build(l, mid, s)
        build(mid + 1, r, s)
    
    # 判断当前区间的类型
    segment = s[l:r + 1]
    if all(c == '0' for c in segment):
        print('B', end='')
    elif all(c == '1' for c in segment):
        print('I', end='')
    else:
        print('F', end='')


def main() -> None:
    n = int(input())
    s = input().strip()
    
    build(0, len(s) - 1, s)
    print()  # 输出换行


if __name__ == '__main__':
    main()

Java

import java.io.BufferedInputStream;
import java.io.InputStream;
import java.util.StringTokenizer;

/**
 * P1087 FBI树 - Java 解法
 */
public class Main {
    static String s;
    
    /**
     * 递归构造 FBI 树并输出后序遍历
     * @param l 区间左端点
     * @param r 区间右端点
     */
    static void build(int l, int r) {
        // 后序遍历：先左，再右，最后根
        if (r > l) {
            int mid = (l + r) / 2;
            build(l, mid);
            build(mid + 1, r);
        }
        
        // 判断当前区间的类型
        boolean allZero = true;
        boolean allOne = true;
        
        for (int i = l; i <= r; i++) {
            if (s.charAt(i) == '0') {
                allOne = false;
            } else if (s.charAt(i) == '1') {
                allZero = false;
            }
        }
        
        // 输出结点类型
        if (allOne) {
            System.out.print('I');
        } else if (allZero) {
            System.out.print('B');
        } else {
            System.out.print('F');
        }
    }
    
    public static void main(String[] args) throws Exception {
        FastScanner sc = new FastScanner();
        int n = sc.nextInt();
        s = sc.next();
        
        build(0, s.length() - 1);
        System.out.println();
    }
    
    /**
     * 快速输入类
     */
    static class FastScanner {
        private BufferedInputStream bis = new BufferedInputStream(System.in);
        private byte[] buffer = new byte[1024];
        private int current = 0;
        private int size = 0;
        
        private int read() throws Exception {
            if (current >= size) {
                size = bis.read(buffer);
                current = 0;
                if (size <= 0) return -1;
            }
            return buffer[current++];
        }
        
        public int nextInt() throws Exception {
            int c = read();
            while (c <= ' ') c = read();
            int result = 0;
            do {
                result = result * 10 + (c - '0');
            } while ((c = read()) >= '0' && c <= '9');
            return result;
        }
        
        public String next() throws Exception {
            int c = read();
            while (c <= ' ') c = read();
            StringBuilder sb = new StringBuilder();
            do {
                sb.append((char) c);
            } while ((c = read()) > ' ');
            return sb.toString();
        }
    }
}

JavaScript

'use strict';

/**
 * P1087 FBI树 - JavaScript 解法
 */

let s;

/**
 * 递归构造 FBI 树并输出后序遍历
 * @param {number} l - 区间左端点
 * @param {number} r - 区间右端点
 */
function build(l, r) {
    // 后序遍历：先左，再右，最后根
    if (r > l) {
        const mid = Math.floor((l + r) / 2);
        build(l, mid);
        build(mid + 1, r);
    }
    
    // 判断当前区间的类型
    let allZero = true;
    let allOne = true;
    
    for (let i = l; i <= r; i++) {
        if (s[i] === '0') allOne = false;
        if (s[i] === '1') allZero = false;
    }
    
    // 输出结点类型
    if (allOne) {
        process.stdout.write('I');
    } else if (allZero) {
        process.stdout.write('B');
    } else {
        process.stdout.write('F');
    }
}

function main() {
    const fs = require('fs');
    const data = fs.readFileSync(0, 'utf-8').trim().split(/\s+/);
    
    // 第一个是 n，第二个是字符串 s
    s = data[1];
    
    build(0, s.length - 1);
    process.stdout.write('\n');
}

main();

类似题目