FBI树

• 2020 年 4 月 9 日
• 筆記

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