FBL树 题解

按题意模拟

后序遍历：先左儿子，后右儿子，最后根

同理类推

先序遍历：先根，再左儿子，后右儿子

中序遍历：先左儿子，再根，最后右儿子

AC代码

#include<bits/stdc++.h>
using namespace std;
int n,cnt=0,lp,rp,lpp,rpp,len;
char a[1300],tree[10000];
int create(int l,int r){
	int mid=l+r>>1;
	if(r==l){//直到分到一个数为止
		tree[++cnt]=a[l];
		return cnt;
	}
	int L=create(l,mid);//递归处理左半段
	int R=create(mid+1,r);//递归处理右半段
	if(tree[L]==tree[R]) tree[++cnt]=tree[R];
	else tree[++cnt]='2';
	return cnt;
}
int main(){
	scanf("%d",&n);
	scanf("%s",a);
	len=strlen(a);
	if(len==1){
		if(a[0]=='0') printf("B");
		else printf("I");
		return 0;
	}
	create(0,len-1);
	for(int i=1;i<=cnt;++i)
	{
		if(tree[i]=='0') printf("B");
		if(tree[i]=='1') printf("I");
		if(tree[i]=='2') printf("F");
	}
	return 0;
}