算法
(递归,二叉树) $O((N+1)2^N)$
对于样例来说,我们可以得到如下所示的满二叉树:
可以递归处理整棵树,我们发现当输入字符串固定时,整棵树也就固定了,因此可以将字符串当做递归函数传入的参数。
由于要输出后序遍历,因此需要先输出左子树和右子树,再输出当前节点的信息。
从图中可以发现,左子树所对应的字符串即是当前字符串的前半段,右子树所对应的字符串是后半段。因此依次递归处理字符串的前半段和后半段即可。
最后需要判断当前节点的类型,这里可以统计一下当前字符串中0和1的包含情况。
时间复杂度
在每个递归函数内判断当前节点的类型时,均需要遍历一遍整个字符串,因此时间复杂度是线性的。从上图中可以发现,整棵树一共有 $N + 1$ 层,每层总共会遍历 $O(N)$ 的长度,因此总时间复杂度是 $O(N + 1)2^N)$。
另外如果 $N$ 的范围扩大,我们可以用前缀和思想来加速最后一步的效率,即判断当前节点信息这一步的效率,可以将时间复杂度优化至 $O(2^N)$。
C++ 代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
void dfs(string str)
{
if (str.size() > 1)
{
dfs(str.substr(0, str.size() / 2));
dfs(str.substr(str.size() / 2));
}
int one = 0, zero = 0;
for (int i = 0; i < str.size(); i ++ )
if (str[i] == '0') zero ++ ;
else one ++ ;
if (one && zero) cout << 'F';
else if (one) cout << 'I';
else cout << 'B';
}
int main()
{
int n;
string str;
cin >> n >> str;
dfs(str);
return 0;
}