LeetCode 95：不同的二叉搜索樹 II —— 遞歸生成所有結構

題目

給定 n，生成所有鍵值為 1...n 的結構不同的二叉搜索樹（BST）。返回所有可能的樹根節點列表。

範例

n = 3 時共有 5 棵不同結構的 BST：

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

解題思路：遞歸構造

與「不同的二叉搜索樹 I」（只求數量，用 Catalan 數 DP）不同，本題需顯式構造每棵樹，子問題不重疊，無法用 DP 優化時間，複雜度本質上是 O(C_n)（Catalan 數級別）。

遞歸策略

• 枚舉根節點值 root = 1..n。
• 左子樹由 1..root-1 遞歸生成所有可能。
• 右子樹由 root+1..n 遞歸生成所有可能（值需 +root 偏移）。
• 對左、右子樹列表做笛卡爾積組合，拼接到新根節點。

關鍵細節

• 基例：n == 0 返回 {nullptr}；n == 1 返回單節點樹。
• 使用 base 參數傳遞值偏移，避免重複創建節點值。
• 記憶化（unordered_map）可緩存相同 (n, base) 的結果，但本題 base 不同導致緩存命中率低，通常不加也能 AC。

完整代碼（C++）

/**
 * 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 {
private:
    // 可選：記憶化加速
    // unordered_map<long long, vector<TreeNode*>> memo;
    vector<TreeNode*> gen(int n, int base) {
        vector<TreeNode*> res;
        if (n == 0) { res.push_back(nullptr); return res; }
        if (n == 1) { res.push_back(new TreeNode(base + 1)); return res; }
        for (int root = 1; root <= n; ++root) {
            auto leftTrees  = gen(root - 1, base);
            auto rightTrees = gen(n - root, base + root);
            for (auto L : leftTrees) {
                for (auto R : rightTrees) {
                    TreeNode* node = new TreeNode(base + root);
                    node->left = L;
                    node->right = R;
                    res.push_back(node);
                }
            }
        }
        return res;
    }
public:
    vector<TreeNode*> generateTrees(int n) {
        if (n == 0) return {};
        return gen(n, 0);
    }
};

複雜度分析

• 時間：O(C_n)，C_n = (2n)!/((n+1)!n!) 為第 n 個 Catalan 數。
• 空間：O(C_n) 存儲結果 + O(n) 遞歸棧。

體會與拓展

1. 本題是「唯一 BST I」的構造版，思路高度相似，只是返回值從計數變為樹列表。
2. 若只求數量，用 DP dp[n] = Σ dp[i-1]*dp[n-i] 即可 O(n²)。
3. 實際面試中常考：先問數量（Catalan），再問生成所有樹（遞歸+笛卡爾積）。