LeetCode 95 Unique Binary Search Trees II：遞歸構造所有可能 BST

問題描述

給定整數 n，生成所有鍵值為 1...n 的結構不同的二叉搜索樹。例如 n=3 有 5 棵不同的 BST（即第 3 個卡特蘭數）。

核心遞歸思想

BST 性質：左子樹鍵值 < 根 < 右子樹鍵值。對於序列 [start, end]：

1. 枚舉每個 i ∈ [start, end] 作為根節點
2. 遞歸構造左子樹集合 generate(start, i-1)
3. 遞歸構造右子樹集合 generate(i+1, end)
4. 雙重循環組合所有左右子樹對，掛接到根節點

標準遞歸實現

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        if (n == 0) return {};
        return helper(1, n);
    }
    
    vector<TreeNode*> helper(int start, int end) {
        vector<TreeNode*> res;
        if (start > end) {
            res.push_back(nullptr); // 空子樹用 nullptr 表示
            return res;
        }
        for (int i = start; i <= end; ++i) {
            auto leftTrees = helper(start, i-1);
            auto rightTrees = helper(i+1, end);
            for (auto l : leftTrees) {
                for (auto r : rightTrees) {
                    TreeNode* root = new TreeNode(i);
                    root->left = l;
                    root->right = r;
                    res.push_back(root);
                }
            }
        }
        return res;
    }
};

複雜度分析

• 時間：O(C_n)，C_n = (2n)!/((n+1)!n!) 為第 n 個卡特蘭數，輸出大小本身即為指數級
• 空間：O(C_n) 存儲結果 + O(n) 遞歸棧
• 記憶化優化：可用 map 緩存區間結果，但對 LeetCode 規模通常不必要

int numTrees(int n) {
    vector<long> dp(n+1, 0);
    dp[0] = dp[1] = 1;
    for (int i = 2; i <= n; ++i)
        for (int j = 1; j <= i; ++j)
            dp[i] += dp[j-1] * dp[i-j];
    return dp[n];
}