線上OJ 地址：

[04NOIP普及組] FBI樹

本題的意思是：給定一個 01字符串 （對應一棵完全二叉樹的最后一層葉子節點），將樹的每一個節點的值用字母“F、B、I”表示。規則（如下圖所示）為：
1、如果樹的左右子樹的葉子節點都是0，則根節點為B；
2、如果樹的左右子樹的葉子節點都是1，則根節點為 I；
3、如果樹的左右子樹的葉子節點有0也有1，則根節點為 F；

核心思想：
1、由于給出的字符串長度為 $2^N$，所以是滿二叉樹。可以每次 對左右兩半 部分直接進行 遞推建樹
2、使用s.substr對字符串進行截取。substr 接收兩個參數，第一個參數是起始索引，第二個參數是截取長度。如果第二個參數不傳，則默認截取到末尾。
3、牢記輸出樹的模板代碼。核心在于 cout << node[r].val 的位置。這一行放前面就是前序遍歷，放后面就是后續遍歷，放中間就是中續遍歷

題解代碼：

#include <bits/stdc++.h>
using namespace std;const int N = 2100;  // 滿二叉樹，節點總數為2^11 - 1 = 2047struct Node
{int lchild, rchild; // 存儲左子樹和右子樹的節點編號char val;
};
Node node[N];
int n, cnt; // cnt存儲節點數量int creatTree(string s)
{int id = ++cnt;  // 本節點的節點編號if(s.length() == 1) // 如果已經到了葉子節點（無法再分割）{if(s[0] == '0')  node[id].val = 'B';   // 如果葉子為0，則節點編號為Belse if(s[0] == '1')   node[id].val = 'I';  // 如果葉子為1，則節點編號為Ireturn id;}// 若不是邊界，則區分成左右區間，進行遞歸。string s_l = s.substr(0, s.length()/2);  	// 左區間為從 0 開始，長度為 s.length()/2 , 實際到 s.length()/2 - 1。由于s是2^N，所以s.length()/2一定是整數，不存在向下取整string s_r = s.substr(s.length()/2); // 因為左區間到 s.length()/2 - 1，所以右區間為從 s.length()/2 開始，直到末尾node[id].lchild = creatTree(s_l);  // 根據左半段字符串，創建樹，樹的根節點為當前節點的左子樹node[id].rchild = creatTree(s_r);  // 根據右半段字符串，創建樹，樹的根節點為當前節點的右子樹if( node[ node[id].lchild ].val == 'B' && node[ node[id].rchild ].val == 'B' )   node[id].val = 'B';   // 如果左右子樹的值都為B，則當前節點的值也為Belse if( node[ node[id].lchild ].val == 'I' && node[ node[id].rchild ].val == 'I' )   node[id].val = 'I'; // 如果左右子樹的值都為I，則當前節點的值也為Ielse node[id].val = 'F';   // 否則當前節點的值為Freturn id;
}void postOrder(int r)  // 后續遍歷輸出
{if(r == 0)  return;postOrder( node[r].lchild );postOrder( node[r].rchild );cout << node[r].val;   // 關鍵在于這一行。這一行放前面就是前序遍歷，放后面就是后續遍歷，放中間就是中續遍歷
}int main()
{string s;cin >> n >> s;int root = creatTree(s);  // 創建樹postOrder(root);  // 后續遍歷輸出樹return 0;
}