卡特蘭數之不同的二叉搜索樹

• 2020 年 3 月 5 日
• 筆記

在前面寫斐波那契數列的時候，突然想起來卡特蘭數列，所以特地來重溫一下。

什麼是卡特蘭數列

首先這裡給出它的遞推公式  C_n = C₀C_n-1 + C₁C_n-2 + ... + C_n-1C₀

咋一看，看不明白，這就對了，咱來舉幾個例子：

這裡我們先把第一項直接寫出來 C₀ = 1，那麼

C₁ = C₀C₀ = 1 * 1 = 1

C₂ = C₀C₁ + C₁C₀ = 1  + 1  = 2

C₃ = C₀C₂ + C₁C₁ + C₂C₀ = 2  + 1 + 2 = 5

...

高中數學到此為止，再寫得露餡，回到今天的例題。

不同的二叉搜索樹

問題：給定一個整數 n，求以 1 ... n 為節點組成的二叉搜索樹有多少種？

例：輸入n = 3，則結果等於5。5種二叉搜索樹如下：

分析：

這裡我們注意一下二叉搜素樹的性質，滿足當前節點值大於左節點值，小於右節點值的二叉樹才是二叉搜索樹。

假設n個節點的二叉樹搜索樹的個數是G_n，以 i(1 <= i <= n) 為根節點的二叉搜索樹個數定義為F_i，

G_n = F₁ + F₂ + F₃ + ... + F_n

根據搜索樹性質，則當根節點的值為i時, 它的左子樹為由 節點1 到 節點i-1 組成的二叉搜索樹，右子樹為由 節點i + 1 到 節點n 組成的二叉搜素樹。

推到出： F_i = G_i-1 * G_n-i

那麼 G_n = G₀G_n-1 + G₁G_n-2 + G₂G_n-3 + ... + G_n-1G₀

原來G_n 就是卡塔蘭數！

實現：

這裡用的是DP，先計算G₂ ，再計算G₃ ，一直到G_n。 

 1 int CatalanNum(int n) {   2     if(n <= 1){   3         return 1;   4     }   5     int[] dp = new int[n + 1];   6     dp[0] = 1;   7     dp[1] = 1;   8     for(int i = 2; i <= n; i++){   9         for(int j = 1; j <= i; j++){  10             dp[i] += dp[j - 1] * dp[i - j];  11         }  12     }  13     return dp[n];  14 }

時間複雜度：（2 + n) * (n - 1) / 2, 也就是O(N²)。

空間複雜度：dp數組，O(N)。

通項公式：

果然，數學家又給出了通項公式：

 程式碼實現：

int CatalanNum (int n) {      if(n == 0){          return 1;      }      int[] dp = new int[n + 1];      dp[0] = 1;      for(int i = 0; i < n; i++){          dp[i + 1] = dp[i] * 2*(2 * i + 1) / (i + 2);      }      return dp[n];  }

時間複雜度：（O(N)。

空間複雜度：dp數組，O(N)。（可以優化到O(1), 為什麼我每次都不優化。。。）

最後提醒一下：卡特蘭數增長非常快，建議使用大數類型。

PS:

最近看到很多簡歷都提到了Dijkstra，哇塞，真的很亮眼。下次寫它。

End