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