python/TangDou/XiTi/1406.cpp

#include <bits/stdc++.h>

using namespace std;


//说白了，一切递归都是通过这个字符串进行构建树的，只不过在一直玩子串
string s;

// 还需要反复思考，体会其中的意思
// 本题目录入错误，不是2N，应该是2^N

/**
 * 功能：递归构建的核心函数
 * @param x 从第几个开始
 * @param y 到第几个结束
 */
void BuildTree(int x, int y) {
    //cout << "x=" << x << ",y=" << y << endl;
    //如果一样，代表是叶子节点,就是同一个位置,这个是递归的终点，也可以理解为出口
    if (x == y) {
        if (s[x] == '0')
            cout << "B";
        else
            cout << "I";
    } else {
        //进入这里，代表子串还够长，需要继续递归下去~

        // 找到字符串的中点,注意这里面二分法的起止点选择办法
        // x是从0开始的，y是长度-1
        // 数字：1 2 3 4 5 6 7 8
        // 索引：0 1 2 3 4 5 6 7
        // 上面的序列是偶数个，那么  (y-x-1)/2= (7-0-1)/2=3,即索引为3的是一半的位置，0-3，4-7,这是真正的一家一半
        int mid = (y - x - 1) / 2;

        //构建前一半
        BuildTree(x, x + mid);      // 0+3=3,0--->3 就是 0,1,2,3，正好是4个。

        //构建后一半
        BuildTree(x + mid + 1, y);  // 7-3=4,4--->7 就是 4,5,6,7，也是正好4个。

        // 如果是奇数个数字的序列
        // 数字： 1 2 3 4 5 6 7 8 9
        // 索引： 0 1 2 3 4 5 6 7 8
        // 那么  (y-x-1)/2= (8-0-1)/2=3,即索引为3的是一半的位置，0-3，4-8
        // x---> x+mid    0--->3
        // x+mid+1---->y  0+3+1--->8    4--->8

        // 后序遍历开始，其实是要输出了，那么需要怎么输出呢？这取决于它的左右孩子是不是省心！
        // 啥样是省心呢？1孩子数和0孩子数一样就是省心，否则就是不省心。
        // 那怎么才能知道左边的孩子数和右边的孩子数呢？这个也不掌握啊~，这需要从原始的、已有的信息中获取了，在递归中无法知道，原始已有的信息是那个字符串s~~~

        //中间节点最后输出，也就意味着是后序输出
        int cnt0 = 0, cnt1 = 0; //cnt0:0的个数 cnt1:1的个数,
        //计算这段子串中有几个0，几个1
        for (int i = x; i <= y; ++i) {
            if (s[i] == '0')
                cnt0++;
            else
                cnt1++;
        }
        //全是1，那么输出I
        if (cnt0 == 0)
            cout << "I";
        else if (cnt1 == 0) //如果全是0，那么输出B
            cout << "B";
        else  //都有的话，输出F
            cout << "F";
    }
}

int main() {
    int n; //这个n是个废物
    //读入多组数据,以0为截止符
    cin >> n >> s;
    //调用递归函数进行构建,x->y代表字符串的起止位置,因为用到了折半递归，一般的思路是写一个递归函数，将开始和结束的索引号传入，在递归中折半进行。
    BuildTree(0, s.size() - 1);
    return 0;
}