题意

给一个 01 串，代表一棵树的叶节点，输出这棵树的后续遍历

思路

树的经典遍历

直接二分下去，到叶节点就输出+返回；非叶节点就根据两边的子串输出+返回

代码

#include <bits/stdc++.h>
using namespace std;
char a[1030];
int fbi(int l,int r){
	if (l == r){	// 长度为 1 时
		if (a[l] == '0'){
			cout << 'B';
			return 0;
		}else{
			cout << 'I';
			return 1;
		}
	}
	int mid = l + r >> 1;
	int b = fbi(l,mid),c = fbi(mid + 1,r);	// 二分
	if (b == 0 && c == 0){	// 两个子串都是 0
		cout << 'B';
		return 0;
	}else if (b == 1 && c == 1){	// 两个子串都是 1
		cout << 'I';
		return 1;
	}else{	// 01 都有
		cout << 'F';
		return 2;
	}
}
int main(int argc, char **argv){
	int n;
	cin >> n;
	int n2 = 1 << n;	// 2^N
	for (int i = 1;i <= n2;i++){
		cin >> a[i];
	}
	fbi(1,n2);
	return 0;
}

AC呆马

#include<bits/stdc++.h>
using namespace std;
string s;
char arr[int(1e5)];
int t=0;
void dfs(int l,int r){
    bool bflag=0,iflag=0,flag=0;
    if(l>r) return;
    if(l==r) flag=1;//如果只剩下一个字符的话就不往下分了
    for(int i=l;i<=r;i++){//检查字符串中是否有01
        if(s[i]=='1') iflag=1;
        if(s[i]=='0') bflag=1;
    }
    int i=t;
    if(iflag==1 && bflag==1) arr[t++]='F';
    if(iflag==0 && bflag==1) arr[t++]='B';
    if(iflag==1 && bflag==0) arr[t++]='I';
    if(!flag){//剩下一个字符不继续了但需要输出
        int mid=(l+r)/2;
        dfs(l,mid);//后序遍历先遍历左子树
        dfs(mid+1,r);
    }
    cout<<arr[i];//因为是后续遍历所以最后输出自己
}
int main(){
    int n;
    cin>>n;
    cin>>s;
    n=s.size();
    dfs(0,n-1);
    //for(int i=t-1;i>=0;i--) cout<<arr[i];
    return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
string s="";
string C(string x){
	bool is1,is0;
	is1=is0=0;
	for(int i=0;i<x.size();i++){
		if(x[i]=='1') is1=1;
		if(x[i]=='0') is0=1;
	}
	if(is1&&is0) return "F";
	if(is0&&!is1) return "B";
	if(is1&&!is0) return "I";
	return "";
}//判断字符类型 
void dfs(string aa,int len,string type){
	if(len==1){
		cout<<C(aa);
		//特殊情况 
		return;
	}
	string xx="";//作为临时变量存字符串 
	
	//左边 
	for(int i=0;i<len/2;i++) xx+=aa[i];
	if(len)dfs(xx,len/2,C(xx));
	
	
	xx="";//重置xx 
	
	//右边 
	for(int i=len/2;i<aa.size();i++) xx+=aa[i];
	if(len)dfs(xx,len/2,C(xx));
	
	
	cout<<type;
	//因为是后序所以输出放最后 
}
signed main(){
	cin>>n;
	cin>>s;
	dfs(s,pow(2,n),"");
	//递归 
	if(s.size()>1) cout<<"F";
	//特判输出F 
	return 0;
}

这道题的难点在于两个特判

容易漏的是第二个因为基本上不会有一个字符的测试数据