P1087 FBI树 （DFS&二叉树)

P1087 FBI树 （DFS&二叉树)

题目传送门

题意：给定01串,按照给定(FBI)定义输出后序遍历。

思路：二叉树遍历DFS的裸题，写个转换函数就好了。

#include<bits/stdc++.h>
using namespace std;
char jg(string a){//转换函数 
	int x=0,y=0;
	for(int i=0;i<a.size();i++){
		if(a[i]=='0') x++;
		else  y++;
	}
	if(x&&y)  return 'F';
	if(x&&!y) return 'B';
	if(!x&&y) return 'I';
}
void dfs(string a){
	int l=a.size(); 
	if(l==1){ //结束条件. 
		cout<<jg(a);
		return;
	}
	dfs(a.substr(0,l>>1));//满足后序遍历的顺序。 
	dfs(a.substr(l>>1));
	cout<<jg(a);
}
int main(){
	int n,x=0,y=0;
	cin>>n;
	string a;
	cin>>a;
	dfs(a);
	puts("");
	return 0;
}