給定整數 n，回傳由 1 到 n 組成的所有結構不同的 BST。以任意順序回傳。
Example:
Input: n = 3 Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
Intuition
TIP
枚舉每個數字作為根，遞迴生成所有可能的左右子樹，再組合起來。
- 與 96 題思路相同，但需要實際建構所有樹
- 以 i 為根，左子樹由 [start, i-1] 生成，右子樹由 [i+1, end] 生成
- 將所有左右子樹的組合配對，形成不同的 BST
Approaches
1. Recursive Enumeration — O(n * C(n)) / O(n * C(n))
- Idea: 枚舉區間內每個數字作為根，遞迴生成左右子樹列表，交叉組合
- Time:
O(n * C(n))，C(n) 為卡塔蘭數 - Space:
O(n * C(n))
class Solution {
fun generateTrees(n: Int): List<TreeNode?> {
if (n == 0) return emptyList()
return generate(1, n)
}
private fun generate(start: Int, end: Int): List<TreeNode?> {
if (start > end) return listOf(null)
val result = mutableListOf<TreeNode?>()
for (i in start..end) {
val leftTrees = generate(start, i - 1)
val rightTrees = generate(i + 1, end)
for (left in leftTrees) {
for (right in rightTrees) {
val root = TreeNode(i)
root.left = left
root.right = right
result.add(root)
}
}
}
return result
}
}⭐ 2. Recursion + Memoization — O(n * C(n)) / O(n * C(n))
- Idea: 用 HashMap 快取已計算過的區間結果，避免重複遞迴
- Time:
O(n * C(n)) - Space:
O(n * C(n))
class Solution {
private val memo = HashMap<Pair<Int, Int>, List<TreeNode?>>()
fun generateTrees(n: Int): List<TreeNode?> {
if (n == 0) return emptyList()
memo.clear()
return generate(1, n)
}
private fun generate(start: Int, end: Int): List<TreeNode?> {
if (start > end) return listOf(null)
val key = start to end
memo[key]?.let { return it }
val result = mutableListOf<TreeNode?>()
for (i in start..end) {
val leftTrees = generate(start, i - 1)
val rightTrees = generate(i + 1, end)
for (left in leftTrees) {
for (right in rightTrees) {
val root = TreeNode(i)
root.left = left
root.right = right
result.add(root)
}
}
}
memo[key] = result
return result
}
}Watch Out: Shared Subtree
在 memoization 版本中，不同的樹可能共用相同的子樹節點。這在只讀取的情境下沒有問題，但如果需要修改樹的結構，則需要做深拷貝。LeetCode 的判題系統不會修改樹，所以共用是安全的。
🔑 Takeaways
- Pattern: 枚舉根 + 遞迴生成子樹 + 交叉組合，是生成所有 BST 的標準模板
- Key trick: base case 回傳
listOf(null)而非空列表，確保父節點能正確配對 null 子樹