题目描述
构造FBI树,根据输入的串通过递归方式来进行左、右子树搜索遍历
1)递归运算;
2) 若可以再分,继续递归左子树,以及右子树递归
3) 然后进行自身判断
细节以及小技巧
1)位运算划分左、右子树
2)最后让我们输出此FBI树的后续遍历我们必须要特别处理
a.后续遍历 左右根
b.递归遍历搜索,左子树、右子树、根,所以输出即为后序遍历
样例
输入样例:
3
10001011
输出样例:
IBFBBBFIBFIIIFF
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
int n;
void dfs(int n,string str){
if(n>0){
dfs(n-1,str.substr(0,1 << n - 1));
dfs(n-1,str.substr(1 << n - 1));
}
int one = 0,zero = 0;
for(int i = 0; i<str.size(); i++){
if(str[i]=='0') zero++;
else one++;
}
if(zero&&one) cout << "F";
else if(zero) cout << "B";
else cout << "I";
}
int main(){
string str;
cin >> n >> str;
dfs(n,str);
return 0;
}