LeetCode 95 Unique Binary Search Trees II：生成所有結構不同的 BST

題目描述

給定 1..n，生成所有由這 n 個節點構成的、結構不同的二叉搜索樹，返回根節點列表。

範例

n = 3 輸出 5 棵樹：
  1         3     3      2      1
   \       /     /      / \      \
    3     2     1      1   3      2
   /     /       \                 \
  2     1         2                 3

遞歸 + 備忘錄解法

核心思想

• 對於序列 start..end，枚舉每個 root 作為根節點。
• 左子樹由 start..root-1 構成，右子樹由 root+1..end 構成。
• 左右子樹組合的笛卡爾積即為以 root 為根的所有樹。
• 相同區間重複計算 → 用 map, vector> 緩存。

Python 參考實作

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def generateTrees(self, n):
        if n == 0: return []
        self.cache = {}
        return self._generate(1, n)
    
    def _generate(self, start, end):
        if (start, end) in self.cache:
            return self.cache[(start, end)]
        
        roots = []
        for root_val in range(start, end + 1):
            for left in self._generate(start, root_val - 1):
                for right in self._generate(root_val + 1, end):
                    node = TreeNode(root_val)
                    node.left = left
                    node.right = right
                    roots.append(node)
        
        self.cache[(start, end)] = roots or [None]
        return self.cache[(start, end)]

C++ 版本要點

• 返回 vector，需注意記憶體管理（競賽環境通常忽略釋放）。
• 緩存用 map, vector> 或 vector>。
• 基礎情況：start > end 返回 {nullptr}。

複雜度

• 時間/空間：卡特蘭數 C_n = (2n)!/((n+1)!n!)，輸出敏感，無法進一步優化。
• 備忘錄避免重複構建相同子樹結構，但最終輸出大小仍為卡特蘭數級別。

關鍵點

1. BST 性質：左子樹值 < 根 < 右子樹值，天然對應有序序列分割。
2. 遞歸分治 + 組合展開 + 備忘錄 = 標準解法。
3. 區別於 LC 96（只求數量），本題需實際構建樹結構。