題目描述:
給定整數 n,生成所有由 1 到 n 組成的結構唯一的二元搜尋樹(BST),回傳所有根節點的列表。
解題思路:
使用遞迴分治法。對於值域 [start, end] 中的每個值 i,將 i 作為根節點:
[start, i-1] 的所有左子樹。[i+1, end] 的所有右子樹。i 為根的完整 BST。基礎情況:當 start > end 時,回傳 [nullptr](空子樹)。
這本質上是 Catalan 數的結構枚舉,每棵樹都是合法的 BST。
時間複雜度: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) 的結果。減少重複遞迴呼叫,但注意子樹是共享的,修改時需小心。時間上有常數優化但漸近複雜度相同。