洛谷 P1087 FBI树

题目大意：

已知一棵树由字符串组成，

规定：

若节点全1 把这节点称为I节点。

若节点全0 把节点称为B节点。

若节点含0同时含1 把节点称为F节点。

现在有一个字符串N长，左子树是前一半字符串，右子树是后一半字符串。最小的分解节点为一个字符的字符串。我们保证字符串的长度是2的次幂。

求这棵树的后序遍历。

解题思路：

这种树的遍历题目，我们通过数组的下标传进去dfs来进行树的遍历。直接模拟即可。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1024+10;
int arr[MAXN];
void dfs(int l,int r){
  if(l==r){
    if(arr[l]==1)cout<<"I";
    else cout<<"B";
    return ;
  }
  int m=l+(r-l)/2;
  dfs(l,m);
  dfs(m+1,r);
  int res[2]={0};
  for(int i=l;i<=r;i++)
  {
    res[arr[i]]++;
  }
  if(res[0]!=0&&res[1]!=0)cout<<"F";
  else if(res[0]!=0)cout<<"B";
  else cout<<"I";
}
int main(){
  int n;cin>>n;
  string str;
  getline(cin,str);
  getline(cin,str);
  for(int i=0;i<(int)str.size();i++){
    arr[i+1]=str[i]-'0';
  }
  dfs(1,pow(2,n));
  cout<<endl;
  return 0;
}