Link: nowcoder-1086-A

FBI树
Description: 我们可以把由“0”和“1”组成的字符串分为三类:全“0”串称为B串,全“1”串称为I串,既含“0”又含“1”的串则称为F串。

FBI树是一种二叉树[1],它的结点类型也包括F结点,B结点和I结点三种。由一个长度为2^N的“01”串S可以构造出一棵FBI树T,递归的构造方法如下:

1) T的根结点为R,其类型与串S的类型相同;

2) 若串S的长度大于1,将串S从中间分开,分为等长的左右子串S1和S2;由左子串S1构造R的左子树T1,由右子串S2构造R的右子树T2。

现在给定一个长度为2N的“01”串,请用上述构造方法构造出一棵FBI树,并输出它的后序遍历[2]序列。

[1] 二叉树:二叉树是结点的有限集合,这个集合或为空集,或由一个根结点和两棵不相交的二叉树组成。这两棵不相交的二叉树分别称为这个根结点的左子树和右子树。

[2] 后序遍历:后序遍历是深度优先遍历二叉树的一种方法,它的递归定义是:先后序遍历左子树,再后序遍历右子树,最后访问根。

输入描述:
第一行是一个整数N(0 <= N <= 10)
第二行是一个长度为2^N的“01”串。
输出描述:
一个字符串,即FBI树的后序遍历序列。
示例1
输入
3
10001011
输出
IBFBBBFIBFIIIFF
备注:
对于40%的数据,N <= 2;
对于全部的数据,N<= 10。

Problem solving:
这道题我一开始是没看懂的。但是在csdn上看到了一张巨巨的图。这里借用一下(手动@wwwwcw

看了这个图首先题意不是问题了。我想到了暴力遍历每一个子串。但是太难写了。看到了巨巨的dfs版本。忽然看到了新世界。
我们dfs的时候传两个参数,一个左端点一个右端点。每次去中间的值,如果r和l不相等,就继续dfs,但是这次dfs需要两个,一个是左边(即l-mid),另一个是右边(mid+1,r),如果dfs的过程中r与l相等了,就判断这次l和r之间的01组成,输出对应的字符。这道题还涉及到了基础的二叉树。虽然对这个不太了解,但是对这个题影响不大。

这道题给我最大的感觉就是让我加深了对dfs的理解。

Code:

#include <bits/stdc++.h>
using namespace std;
int n; string s;
void dfs(int l, int r)
{
    int mid = (l + r) / 2;
    if (r != l)
    {
        dfs(l, mid);
        dfs(mid + 1, r);
    }
    int x, y;
    x = y = 0;
    for (int i = l; i <= r; i++)
    {
        if (s[i] - '0' == 0)
            x++;
        else
            y++;
    }
    if (x && y)
        cout << "F";
    if (x && !y)
        cout << "B";
    if (!x && y)
        cout << "I";
}
int main()
{
    cin >> n >> s;
    dfs(0, s.size() - 1);
    return 0;
}

dfs是真的妙!!!