NC16660 FBI树 递归
链接：https://ac.nowcoder.com/acm/problem/16660
来源：牛客网
题目描述
我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。
FBI树是一种二叉树[1]，它的结点类型也包括F结点，B结点和I结点三种。由一个长度为2N的“01”串S可以构造出一棵FBI树T，递归的构造方法如下：
-
T的根结点为R，其类型与串S的类型相同；
-
若串S的长度大于1，将串S从中间分开，分为等长的左右子串S1和S2；由左子串S1构造R的左子树T1，由右子串S2构造R的右子树T2。
现在给定一个长度为2N的“01”串，请用上述构造方法构造出一棵FBI树，并输出它的后序遍历[2]序列。[1] 二叉树：二叉树是结点的有限集合，这个集合或为空集，或由一个根结点和两棵不相交的二叉树组成。这两棵不相交的二叉树分别称为这个根结点的左子树和右子树。
[2] 后序遍历：后序遍历是深度优先遍历二叉树的一种方法，它的递归定义是：先后序遍历左子树，再后序遍历右子树，最后访问根。
输入描述:
第一行是一个整数N（0 <= N <= 10）
第二行是一个长度为2N的“01”串。
输出描述:
一个字符串，即FBI树的后序遍历序列。
示例1
输入
复制
3
10001011
输出
复制
IBFBBBFIBFIIIFF
备注:
对于40%的数据，N <= 2；
对于全部的数据，N<= 10。
递归即可
类似于线段树的build操作
#define debug
#ifdef debug
#include <time.h>
#include "/home/majiao/mb.h"
#endif
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <math.h>
#define MAXN ((int)1e6+7)
#define ll long long int
#define INF (0x7f7f7f7f)
#define fori(lef, rig) for(int i=lef; i<=rig; i++)
#define forj(lef, rig) for(int j=lef; j<=rig; j++)
#define fork(lef, rig) for(int k=lef; k<=rig; k++)
#define QAQ (0)
using namespace std;
#ifdef debug
#define show(x...) \ do { \ cout << "\033[31;1m " << #x << " -> "; \ err(x); \ } while (0)
void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
#endif
#ifndef debug
namespace FIO {
template <typename T>
void read(T& x) {
int f = 1; x = 0;
char ch = getchar();
while (ch < '0' || ch > '9')
{ if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9')
{ x = x * 10 + ch - '0'; ch = getchar(); }
x *= f;
}
};
using namespace FIO;
#endif
int n, m, Q, K;
char buf[MAXN];
int build(int lef, int rig) {
if(lef == rig) {
printf("%c", buf[lef]=='0' ? 'B' : 'I');
return buf[lef]=='0' ? 'B' : 'I';
}
int mid = (lef + rig) >> 1;
int lch = build(lef, mid);
int rch = build(mid+1, rig);
if(lch==rch && lch=='B') {
printf("B");
return 'B';
}
if(lch==rch && lch=='I') {
printf("I");
return 'I';
}
if(lch != rch) {
printf("F");
return 'F';
}
}
int main() {
#ifdef debug
freopen("test", "r", stdin);
clock_t stime = clock();
#endif
scanf("%d %s ", &n, buf+1);
n = 1<<n;
build(1, n);
#ifdef debug
clock_t etime = clock();
printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif
return 0;
}