Skip to content

1118: FBI树(fbi)

题目

题目描述

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

$FBI$树是一种二叉树,它的结点类型也包括$F$结点,$B$结点和$I$结点三种。由一个长度为$2^N$的“01”串$S$可以构造出一棵$FBI$树$T$,递归的构造方法如下:

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

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

下图是一颗$FBI$树的例子:

输入格式

输入的第一行是一个整数N($0 \leq N \leq 10$),第二行是一个长度为$2^N$的“01”串。

输出格式

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

样例输入

3 10001011

样例输出

IBFBBBFIBFIIIFF

数据范围

对于40%的数据,$N \leq 2$; 对于100%的数据,$N \leq 10$。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!