Medium
95. Unique Binary Search Trees II
dynamic-programmingbacktrackingtreebinary-search-treebinary-tree
解題說明
Unique Binary Search Trees II
題目描述：
給定整數 n，生成所有由 1 到 n 組成的結構唯一的二元搜尋樹（BST），回傳所有根節點的列表。
解題思路：
使用遞迴分治法。對於值域 [start, end] 中的每個值 i，將 i 作為根節點：
- 遞迴生成
[start, i-1]的所有左子樹。 - 遞迴生成
[i+1, end]的所有右子樹。 - 將所有左子樹與右子樹的組合配對，建立以
i為根的完整 BST。
基礎情況：當 start > end 時，回傳 [nullptr]（空子樹）。
這本質上是 Catalan 數的結構枚舉，每棵樹都是合法的 BST。
C++ 解法
複雜度分析
時間複雜度：O(n * C(n)) — C(n) 是第 n 個 Catalan 數（約 4^n / n^(3/2)），每棵樹有 n 個節點需要建立。
空間複雜度：O(n * C(n)) — 需要儲存所有 C(n) 棵樹，每棵有 n 個節點。遞迴深度為 O(n)。
虛擬碼
1. Define build(start, end):
a. If start > end, return [null]
b. Initialize result = []
c. For each i from start to end:
- lefts = build(start, i - 1)
- rights = build(i + 1, end)
- For each left in lefts, each right in rights:
* Create node with val=i, left=left, right=right
* Append to result
d. Return result
2. Call build(1, n) and return result其他解法
動態規劃 + 偏移量複製：先建立 [1..k] 的所有 BST（自底向上 DP），對於 [start..end] 透過複製 [1..end-start+1] 的樹並加上偏移量。可以避免重複計算子問題，但複製樹的開銷使實際效率差異不大。
Memoization 遞迴：用 map<pair<int,int>, vector<TreeNode*>> 快取 build(start, end) 的結果。減少重複遞迴呼叫，但注意子樹是共享的，修改時需小心。時間上有常數優化但漸近複雜度相同。
延伸思考
- 如果只需要計算不同 BST 的數量而非生成它們，如何用 O(n) 空間的 DP 求解？（LeetCode 96）
- 生成的樹之間可能共享子樹節點，這在記憶體管理上有什麼影響？如何確保正確的記憶體釋放？
- 若 n 很大（如 n=20），Catalan 數增長極快，有什麼策略可以只生成前 k 棵樹？