FBI树

通过递归构造二叉树，根据字符串类型确定节点类型，再对构造的树进行后序遍历输出结果

#include<bits/stdc++.h>
using namespace std;

struct FBINode {
    char type; // 节点类型
    FBINode* left; 
    FBINode* right; 
    FBINode(char t) : type(t), left(nullptr), right(nullptr) {}
};
// 判断字符串对应的节点类型
char getNodeType(const string& s) {
    bool has0 = false, has1 = false;
    for (char c : s) {
        if (c == '0') has0 = true;
        else has1 = true;
        if (has0 && has1) return 'F'; // 1和0F
    }
    return has0 ? 'B' : 'I'; // 全0为B，全1为I
}
// 递归构造FBI树
FBINode* build(const string& s) {
    char t = getNodeType(s);
    FBINode* root = new FBINode(t);
    if (s.length() == 1) return root; // 长度1，无左右子树
    
    int mid = s.length() / 2;
    // 分割左右子串，构造左右子树
    root->left = build(s.substr(0, mid));
    root->right = build(s.substr(mid));
    return root;
}
void ans(FBINode* root) {
    if (!root) return;
    ans(root->left);
    ans(root->right);
    cout << root->type;
}

int main(){
    int n;
    string s;
    cin >> n >> s;
    FBINode* root = build(s);
    ans(root);
    return 0;
}

时间复杂度： O(2 ^N )