#NOIPJ2004C. FBI 树

FBI 树

题目描述

我们可以把由 “ 00 ”和“ 11 ”组成的字符串分为三类:全“ 00 ”串称为 BB 串,全“ 11 ”串称为 II 串,既含“ 00 ”又含“ 11 ”的串则称为 FF 串。 FBIFBI 树是一种二叉树。

( 二叉树:二叉树是结点的有限集合,这个集合或为空集,或由一个根结点和两棵不相交的二叉树组成。这两棵不相交的二叉树分别称为这个根结点的左子树和右子树。)

它的结点类型也包括 FF 结点,BB 结点和 II 结点三种。由一个长度为 2N2N 的“ 0101 ”串 SS 可以构造出一棵 FBIFBITT ,递归的构造方法如下: TT 的根结点为 RR ,其类型与串 SS 的类型相同; 若串 SS 的长度大于 11 ,将串 SS 从中间分开,分为等长的左右子串 S1S1S2S2 ;由左子串 S1S1 构造RR 的左子树 T1T1 ,由右子串 S2S2 构造 RR 的右子树 T2T2。 现在给定一个长度为 2N2N 的“ 0101 ”串,请用上述构造方法构造出一棵 FBIFBI 树,并输出它的后序遍历序列。

(后序遍历:后序遍历是深度优先遍历二叉树的一种方法,它的递归定义是:先后序遍历左子树,再后序遍历右子树,最后访问根。)

输入格式

输入文件的第一行是一个整数 NN 0N10(0 \le N \le 10) ,第二行是一个长度为 2N2N 的“ 0101 ”串。

输出格式

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

3
10001011
IBFBBBFIBFIIIFF

数据范围与提示

对于 4040 %的数据,N2N \le 2

对于全部的数据,N10N \le 10