LeetCode 96 Unique Binary Search Trees：卡特蘭數與動態規劃

題目回顧

給定 n，求由 1...n 構成的結構不同的二叉搜索樹（BST）數量。
例：n=3 → 5 棵不同結構的 BST。

核心遞推：卡特蘭數

以 i (1≤i≤n) 為根，左子樹由 [1, i-1] 構成，右子樹由 [i+1, n] 構成。
設 f(k) 為 k 個節點的不同 BST 數，則：

f(0) = 1 (空樹)
f(1) = 1
f(2) = f(0)f(1) + f(1)f(0) = 2
f(3) = f(0)f(2) + f(1)f(1) + f(2)f(0) = 5
...
f(n) = Σ f(i-1) * f(n-i)  (i=1..n)

這正是卡特蘭數：C_n = (2n)! / ((n+1)! n!)

動態規劃實現

class Solution {
public:
    int numTrees(int n) {
        vector dp(n + 1, 0);
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; ++i) {
            for (int k = 1; k <= i; ++k) {
                dp[i] += dp[k - 1] * dp[i - k];
            }
        }
        return dp[n];
    }
};

數學公式 O(n) 計算（防溢出用長整型）

class Solution {
public:
    int numTrees(int n) {
        long long catalan = 1;
        for (int i = 0; i < n; ++i) {
            catalan = catalan * 2 * (2 * i + 1) / (i + 2); // C_{i+1} = C_i * 2(2i+1)/(i+2)
        }
        return (int)catalan;
    }
};

複雜度

圖解 n=3 的 5 棵 BST

延伸：LeetCode 95 生成所有 BST

若需生成所有結構，需遞歸構建左右子樹列表並組合，時間空間均為卡特蘭數級別。