LeetCode 95 不同的二叉搜索樹 II：遞歸構造所有合法 BST 完整解析

問題重述

給定整數 n，生成所有鍵值為 1..n 且結構不同的二叉搜索樹，返回根節點列表。例如 n=3 有 5 棵樹（卡特蘭數）。

遞歸核心思想

對於區間 [l, r]，枚舉根節點 i ∈ [l, r]：
左子樹集合 = generate(l, i-1)
右子樹集合 = generate(i+1, r)
對左、右集合做笛卡爾積組合，每對構造一棵以 i 為根的樹。

基礎遞歸實現（含空指針判斷）

vector helper(int l, int r) {
    vector res;
    if (l > r) { res.push_back(nullptr); return res; } // 關鍵：返回含 nullptr 的向量
    if (l == r) { res.push_back(new TreeNode(l)); return res; }

    for (int i = l; i <= r; ++i) {
        auto left = helper(l, i-1);
        auto right = helper(i+1, r);
        for (auto ln : left)
            for (auto rn : right) {
                TreeNode* root = new TreeNode(i);
                root->left = ln;
                root->right = rn;
                res.push_back(root);
            }
    }
    return res;
}

優化技巧：統一空指針處理

將 l > r 時返回 {nullptr}，消除顯式 if (left.empty()) 分支，代碼更簡潔，邏輯統一。

複雜度分析

• 時間：O(C_n)，C_n 為第 n 個卡特蘭數（指數級）。
• 空間：遞歸棧 O(n) + 結果樹總節點數 O(n * C_n)。

記憶化優化（可選）

用 map, vector> 緩存區間結果，避免重複計算，但會增加內存佔用。

內存管理提醒

LeetCode 由判題系統回收內存，實際工程中需提供銷毀函數遞歸 delete 所有節點，防止洩漏。