题解 | #FBI树#

• 题目考点：分治（二分）
• 题目内容：给出一个01串，将其不断二分成一颗二叉树，求后序遍历；遍历过程中，若某一节点儿子均为1，输出‘I’，若均为0，输出‘F’，否则输出‘F’；
• 题目分析：如题目样例：

  3
  10001011

  则有：
  

#include<iostream>
#include<algorithm>

using namespace std;

int n;
string s;

char FBI(int l, int r)
{
    if(l == r) //若已经到了叶子节点，直接返回
    {
        if(s[l] == '0')
        {
            cout<<'B'; return 'B';
        }
        if(s[l] == '1')
        {
            cout<<'I'; return 'I';
        }
    }
    int mid = l + r >> 1; //没有到叶子结点，继续二分
    char sonl = FBI(l+1-1, mid);
    char sonr = FBI(mid + 1, r);
    //根据儿子节点的情况输出并返回
    if((sonl == 'F' || sonr == 'F') || sonl != sonr)
    {
        cout<<'F'; return 'F';
    }
    if(sonl == 'I')
    {
        cout<<'I'; return 'I';
    }
    cout<<'B'; return 'B';
}

int main()
{
    int n;
    cin >> n >> s;
    FBI(0, s.size() - 1);
    return 0;
}