题目描述
我们可以把由 “0” 和 “1” 组成的字符串分为三类：全 “0” 串称为 B 串，全 “1” 串称为 I 串，既含 “0” 又含 “1” 的串则称为 F 串。
FBI树是一种二叉树，它的结点类型也包括 F 结点，B 结点和 I 结点三种。由一个长度为 2^N2N 的 “01” 串 S 可以构造出一棵 FBI 树 T，递归的构造方法如下：
- T 的根结点为 R，其类型与串 S 的类型相同；
- 若串 S 的长度大于 1，将串 S 从中间分开，分为等长的左右子串 S1 和 S2 ；由左子串 S1 构造 R 的左子树 T1，由右子串 S2 构造 R 的右子树 T2。
现在给定一个长度为 2^N2N 的 “01” 串，请用上述构造方法构造出一棵FBI树，并输出它的后序遍历序列。
输入描述
第一行是一个整数 N（0 \leq N \leq 10）N（0≤N≤10）。
第二行是一个长度为 2^N2N 的 “01” 串。
输出描述
输出一个字符串，即 FBI 树的后序遍历序列。
输入输出样例
示例 1
输入
1. 3 2. 10001011
输出
IBFBBBFIBFIIIFF
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
思路：
题目首先要求建树。建树分为两步。第一步，判断当前的字符串的类型，根据题目全 “0” 串称为 B 串，全 “1” 串称为 I 串，既含 “0” 又含 “1” 的串则称为 F 串，写出当前的树节点（对应串的类型）。第二步，将当前串从中间分成两个串，新的串成为第一步的当前串。循环往复，直到最初的字符串被分为一个个字母。
我们在建树过程中可以通过递归调用，先建立叶子节点，这很容易判断，再根据下面一层的F，B，I值判断上面一层的值，全B则B，全C则C,否则为F。
建立好树之后，只需要后序遍历输出即可。
代码：
1. n=int(input()) 2. s=input() 3. #list存储二叉树 4. tree=['']*1000000 5. #运用递归，从下往上建树 6. def build_FBI(k,left,right): 7. if left==right: 8. if s[right]=='1': 9. tree[k]='I' 10. else: 11. tree[k]='B' 12. return 13. mid=(left+right)//2 14. build_FBI(2*k,left,mid) 15. build_FBI(2*k+1,mid+1,right) 16. 17. if tree[2*k]=='B' and tree[2*k+1]=='B': 18. tree[k]='B' 19. elif tree[2*k] == 'I' and tree[2*k+1]=='I' : 20. tree[k]='I' 21. else: 22. tree[k]='F' 23. #后序遍历输出 24. def postorder(v): 25. if tree[2*v]!='': 26. postorder(2*v) 27. if tree[2*v+1]!='': 28. postorder(2*v+1) 29. print(tree[v],end='') 30. #调用函数 31. build_FBI(1,0, len(s)-1) 32. postorder(1)
