0096. Unique Binary Search Tree - chasel2361/leetcode GitHub Wiki

Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?

Example:
Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST's:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3

令這個函式為 f(n)

假設 n = 0：沒得排，所以可能的排法只有一種
f(0) = 1

假設 n = 1：可能的排法只有一種
f(1) = 1

假設 n = 2：根有兩種可能
根 = 1：
左子樹沒東西，其組合數與 n = 0 相同為 f(0)
右子樹只剩下 2 可以放，其組合數與 n = 1 相同為 f(1) 根 = 2：
左子樹只剩下 2 可以放，其組合數與 n = 1 相同為 f(1)
右子樹沒東西，其組合數與 n = 0 相同為 f(0)
f(2) = f(0)*f(1) + f(1)*f(0)

假設 n = 3：根有三種可能
根 = 1：
左子樹沒東西可以放，其組合數與 n = 0 相同為 f(0)
右子樹會是 2, 3 的組合，其組合數為 f(2)
根 = 2：
左子樹有 1 可以放，其組合數為 f(1)
右子樹有 2 可以放，其組合數為 f(1)
根 = 3：
左子樹會是 2, 3 的組合，其組合數為 f(2)
右子樹沒東西可以放，其組合數為 f(0)
f(3) = f(0)*f(2) + f(1)*f(1) + f(2)*f(0)

以此類推可以得知

按照這個邏輯可以用遞迴法寫出這樣的程式碼

class Solution:
    def numTrees(self, n: int) -> int:
        if n == 0 or n == 1: return 1
        total = 0
        for i in range(n):
            total += self.numTrees(i)*self.numTrees(n - i - 1)
        return total

測試過後答案沒問題，但計算會超出時間限制，所以還需要改進寫法

---

參考別人的寫法之後，發現可以利用類似費波納契數列的方式來計算，把前面算出來的值都儲存在陣列裡，要計算新值的時候只要取出舊有的值即可，不必重新計算，計算的程式碼如下：

[1] f(n) 公式
[2] 從 i = 1 計算到 i = n

class Solution:
    def numTrees(self, n: int) -> int:
        res = [0] * (n + 1)
        res[0] = 1
    
        for i in range(1, n + 1):  # [2]
            for j in range(i):  # [1]
                res[i] += res[j] * res[i - j - 1]
        return res[n]

這樣計算的時間複雜度是 O(N^2)，空間複雜度是 O(N)

---

這樣的規律在數學上叫做卡塔蘭數，可以表示為：

所以也可以用數學的方式來解