[LeetCode] 卡特蘭數 & LEETCODE Unique Binary Search Trees

先來看下題目

https://leetcode.com/problems/unique-binary-search-trees/

這題一般來說可以用DP解

我就是一個不會寫DP的人，觀察了下感覺是可以用遞迴之類的解

於是想破了腦看了很久才看出了些端倪

 

這邊引用維基百科：Catalan number

把下一次要新增的Node Leaf看成半月形節點

如果從root 進行BFS由左而右Traverse一次，會發現到最後一個leaf半月形前，內部節點數量始終會大於等於可能新增的leaf節點數量

 

所以這個題目可以等價於高中排列組合題目，一路領先

那種很像階題有格子、問最後有幾種走法的題目。

像是上面那個圖可以看成3個圓形、三個半月型的一路領先的題目

 

以前老師只有教我們直接在格子加，但其實這有公式解的

詳細的proof可以看這篇卡特蘭，我就懶得推了XD

 

把公式變成code會長成這樣，其實還蠻好懂得XD，如果知道這是Catalan Tree又知道這公式應該很快就解完了，不會像我看了一個多小時…XD

class Solution {
public:
    int numTrees(int n) {
        long count = 1;
        for (long i = 1; i <= n; i++) {
            count = count * (i + n) / i;
        }
        return (int)(count / (n+1));
    }
};