95. Unique Binary Search Trees II

Medium

Description

給定整數 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#

枚舉每個數字作為根，遞迴生成所有可能的左右子樹，再組合起來。

與 96 題思路相同，但需要實際建構所有樹
以 i 為根，左子樹由 [start, i-1] 生成，右子樹由 [i+1, end] 生成
將所有左右子樹的組合配對，形成不同的 BST

Approaches#

1: 遞迴枚舉#

概念: 枚舉區間內每個數字作為根，遞迴生成左右子樹列表，交叉組合
時間複雜度: O(n * C(n))，C(n) 為卡塔蘭數
空間複雜度: 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: 遞迴 + Memoization#

概念: 用 HashMap 快取已計算過的區間結果，避免重複遞迴
時間複雜度: O(n * C(n))
空間複雜度: 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
    }
}

注意：子樹共用問題

在 memoization 版本中，不同的樹可能共用相同的子樹節點。這在只讀取的情境下沒有問題，但如果需要修改樹的結構，則需要做深拷貝。LeetCode 的判題系統不會修改樹，所以共用是安全的。

🔑 Takeaways#

Pattern: 枚舉根 + 遞迴生成子樹 + 交叉組合，是生成所有 BST 的標準模板
關鍵技巧: base case 回傳 listOf(null) 而非空列表，確保父節點能正確配對 null 子樹