题目描述

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

FBI树是一种二叉树，它的结点类型也包括F结点，B结点和I结点三种。

由一个长度为2N的“01”串S可以构造出一棵FBI树T，递归的构造方法如下：

1) T的根结点为R，其类型与串S的类型相同；

2) 若串S的长度大于1，将串S从中间分开，分为等长的左右子串S1和S2​；由左子串S1构造R的左子树T1​，由右子串S2构造R的右子树T2。

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

输入格式
第一行是一个整数N。

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

输出格式
包含一行，这一行只包含一个字符串，即FBI树的后序遍历序列。

数据范围
0≤N≤10

输入样例

3
10001010

输出样例

IBFBBBFIBFIIIFF

算法

递归,二叉树
后序遍历就是先看左支，再看右支 最后回到根，再看根的右支的左支.....就这样一直循环。

时间复杂度

O((N+1)2N)

参考文献

可参考大佬的详解：
https://www.acwing.com/solution/acwing/content/5497/
同大佬做的差不多就是在大佬的基础上改的一下，因为还没学str.substr(0, str.size() / 2)就用的下标整数来表示；

C++ 代码

#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
void dfs(string a,int b,int c) {

    if(b!=c) {
        dfs(a,b,(b+c)/2);//左支 
        dfs(a,(b+c)/2+1,c);//右支 
    }
    int one=0,zero=0;//判断'F' 'B' 'I' 
    for(int i=b; i<=c; i++)
        if(a[i]=='0') zero++;
        else if(a[i]=='1') one++;
    if (one && zero) cout << 'F';
    else if (one) cout << 'I';
    else cout << 'B';
}
int main() {
    int n;
    cin>>n;
    string a;
    cin>> a;
    dfs(a,0,((1<<n)-1));//传入a 0为界 ((1<<n)-1)为下界； 
    return 0;
}