题目描述

输入描述

第一行是一个整数N（0<=N<=10）
第二行是一个长度为 2^N 的“01”串。

输出描述

输出一个字符串，即FBI树的后序遍历序列。

输入输出样例

输入：

3
10001011

输出：

IBFBBBFIBFIIIFF

---

最终代码

1. c/c++

#include <bits/stdc++.h>
using namespace std;
char s[2000],tree[280000]; //tree[]存满二叉树



//先叶子节点有值，后根据叶子节点的值确定父节点的值
void build_FBI(int k,int left,int right)
{
         //到达叶子结点
        if(left==right)
        {     
        if(s[right]=='1') tree[k]='I';
        else tree[k]='B';
        return;
        }
        
        int mid=(left+right)/2;      //分成两半
        build_FBI(2*k,left,mid);     //递归左半
        build_FBI(2*k+1,mid+1,right); //递归右半

        if(tree[2*k]=='B' && tree[2*k+1]=='B') //左右儿子都是B
        tree[k]='B';
        else if(tree[2*k]=='I'&&tree[2*k+1]=='I') //左右儿子都是I
        tree[k]='I';
        else tree[k]='F';
}

void postorder (int v){   //后序遍历
        if(tree[2*v])
            postorder (2*v);
        if(tree[2*v+1])
            postorder (2*v+1);

        printf("%c",tree[v]);
}

int main(){
        int n;
        scanf("%d",&n);
        scanf("%s",s+1);
        
        build_FBI(1,1,strlen(s+1));
        
        //后序遍历输出
        postorder(1);
}

---

2. java

---

3. python

---

过程理解