python/TangDou/XiTi/1406_2.cpp

#include <bits/stdc++.h>

using namespace std;

//递推思想，然后利用完全二叉树的性质
string s;
char tree[65536];
int p;

//输出模拟的树，后序
void outhx(int i) {
    //从上向下递归，注意下面不能越界！
    //左边
    if (2 * i <= 2 * p - 1) outhx(2 * i);//2*p-1为节点总数
    //右边
    if (2 * i + 1 <= 2 * p - 1) outhx(2 * i + 1);
    //中间
    cout << tree[i];
    return;
}


int main() {
    int n; //n是树的层数
    cin >> n;
    //小心使的万年船,吃掉回车
    cin.get();
    //输入字符串
    cin >> s;
    p = 1 << n;//p=2的n次方,这比pow()香太多了！左移一位，就是增大2倍，n位就是2的n次方！

    //最后一行，注意这里的s是从0开始的
    for (int i = 0; i < p; i++) {
        if (s[i] == '1')
            tree[i + p] = 'I'; //最底层的元素的位置偏移量，真是牛！
        else tree[i + p] = 'B';
    }
    // 11011000
    // IIBIIBBB



    //从倒数第二层推到第一层
    for (int i = n; i >= 1; i--) {
        //对应的每一层的结点
        for (int j = 1 << (i - 1); j <= (1 << i) - 1; j++) {
            //该节点的左孩子和右孩子是否相等
            if (tree[2 * j] == tree[2 * j + 1]) {
                //孩子啥样，爸爸就啥样
                tree[j] = tree[2 * j];
            } else {
                //混搭！
                tree[j] = 'F';
            }
        }
    }
    //从根开始输出后序遍历
    outhx(1);

    cout << endl;

    //层序输出,tree是从1开始使用的，注意
//    for (int i = 1; i <= 2 * p - 1; ++i) {
//        cout << tree[i];
//    }
    return 0;
}