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是真的妙！！！

赏