審題：

本題需要我們將字符串按照題目要求進行遞歸展開，并按照后序遍歷的順序輸出

思路：

方法一：遞歸

首先我們需要模擬一下題目的意思

其實就是第一步判斷屬于什么字符，然后將字符串分兩半進行下一輪判斷。而由于題目要求按后序遍歷輸出，所以我們就按照后續遍歷的方式進行遞歸調用

疑問：我們如何判斷字符串的情況？

如果我們直接遍歷來判斷會導致時間復雜度過高，所以我們可以采用數值判斷法

假設字符串的每一個索引位置的值相加之和為0，說明字符串都為0，此時為字符'B'。

假設字符串的每一個索引位置的值相加之和等于字符串長度，說明字符串都為1，此時為字符'I'。

其他情況就為字符‘F’

遞歸功能：完成對應索引區間的字符串的后序遍歷字符輸出

解題：
?

#include<iostream>
using namespace std;
const int N = 15;
int f[1 << N];//前綴和數組
int n;
//dfs負責解決區間中所有字符串翻譯與輸出的問題
void dfs(int left, int right)
{//結束條件if (left > right){return;}//判斷當前串的類型char answer;int sum = f[right] - f[left - 1];if (sum == 0) answer = 'B';else if (sum == right - left + 1) answer = 'I';//sum等于串長度else answer = 'F';//按照后序遍歷的方式進行if (left == right)//還剩最后一個字符，若不截斷會死遞歸{cout << answer;return;}int mid = (left + right) / 2;dfs(left, mid); dfs(mid + 1, right);cout << answer;
}
int main()
{cin >> n;n = (1 << n);for (int i = 1; i <= n; i++){char ch;cin >> ch;if (ch == '1') f[i] = f[i - 1] + 1;else f[i] = f[i - 1];}dfs(1, n);return 0;
}

1.我們使用前綴和算法快速的求出對應字符串的sum，前綴和數組存儲的是每一個字符的前綴和的值

2.結束條件：left大于right或left等于right

其中大于的情況下：說明所有字符串都遍歷完了，直接返回

等于的情況：如果不截斷下來會出現死循環，因為mid會等于left。這種情況只剩當前的字符沒有輸出，我們直接輸出當前字符并返回即可

P1087 [NOIP 2004 普及組] FBI 樹 - 洛谷