题目描述

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

FBI树是一种二叉树[1]，它的结点类型也包括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树，并输出它的后序遍历[2]序列。
[1] 二叉树：二叉树是结点的有限集合，这个集合或为空集，或由一个根结点和两棵不相交的二叉树组成。这两棵不相交的二叉树分别称为这个根结点的左子树和右子树。
[2] 后序遍历：后序遍历是深度优先遍历二叉树的一种方法，它的递归定义是：先后序遍历左子树，再后序遍历右子树，最后访问根。

输入描述:

第一行是一个整数N（）
第二行是一个长度为的“01”串。

输出描述:

一个字符串，即FBI树的后序遍历序列。

示例1

输入
3
10001011
输出
IBFBBBFIBFIIIFF

备注

对于40%的数据，；
对于全部的数据，。

解答

分析：

递归枚举当前01串，返回值分三种：

  • 返回1，表示当前01串为I串，即全部为1
  • 返回0，表示当前01串为B串，即全部为0
  • 返回3，表示当前01串为F串，即全部为3

于是你就问了，为什么F串要返回3而不返回-1或2呢

我们先把递归的格式搞清楚，每次递归的是这个01串的左子树与右子树

左子树与右子树有以下几种返回值：

左 0 1 3

右 0 1 3

  • 若左右子树全部返回0，返回值为0时，当前串为B串
  • 若左右子树全部返回1，返回值为2时，当前串为I串
  • 而当前串为F串有许多情况：0+3，1+3，3+3，0+1

你会发现以上值有一个共同特点：不等于0或2

这就是为什么F串返回3

然后就没什么了，在递归过程中按左-右-根的顺序即可

代码如下 

#include<cstring>
#include<iostream>
using namespace std;
char s[(1<<10)+10];
int work(int l,int r)
{
    if(l==r)
    {
        if(s[l]=='0') cout<<"B";
        else cout<<"I";
        return s[l]=='1';
    }
    int sl,sr,m=(l+r)/2;
    sl=work(l,m);
    sr=work(m+1,r);
    if(sl+sr==0)
    {
        cout<<"B";
        return 0;
    }
    else if(sl+sr==2)
    {
        cout<<"I";
        return 1;
    }
    else
    {
        cout<<"F";  
        return 3;
    }
}

int main()
{
    cin>>s>>s;
    work(0,strlen(s)-1);
    return 0;
}



来源：shengzhe