[NOIP 2004 普及组] FBI 树

知识点

分治、二叉树、后序遍历

解题思路

对当前二进制区间：若长度大于1，先递归左半、右半；之后判断区间是否全0、全1或混合，分别输出B、I或F。可用前缀1计数在O(1)判断区间类型。

正确性说明

递归区间与定义的节点一一对应。先处理左、右子树，再输出当前类型，严格遵守后序；区间1的数目为0或区间长度时分别对应全0或全1，其他为F。

易错点

N=0仍有一个叶节点；长度是2^N；不能改成先序输出。

复杂度

设L=2^N，时间O(L)，空间O(L)，递归深度O(N)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
string s;vector<int>p;void dfs(int l,int r){if(l<r){int m=(l+r)/2;dfs(l,m);dfs(m+1,r);}int ones=p[r+1]-p[l];cout<<(ones==0?'B':ones==r-l+1?'I':'F');}int main(){int n;cin>>n>>s;p.resize(s.size()+1);for(int i=0;i<(int)s.size();i++)p[i+1]=p[i]+(s[i]=='1');dfs(0,s.size()-1);cout<<'\n';}