卡特蘭數 & 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