Description
滿二元樹是每個節點要嘛有 0 個子節點、要嘛有 2 個子節點的二元樹。給定整數 n，回傳所有具有 n 個節點的滿二元樹。每棵樹的節點值皆為 0。
Example:
Input: n = 7 Output: [[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]
Intuition#
n 必須是奇數才可能形成滿二元樹；根用 1 個節點，剩餘 n-1 個分配給左右子樹。
- 滿二元樹的節點數一定是奇數（每次增加 2 個子節點）
- 根佔 1 個節點，剩下 n-1 個要分成兩組（各為奇數）給左右子樹
- 左子樹 i 個，右子樹 n-1-i 個，i 從 1 到 n-2（步長 2）
Approaches#
1: 遞迴#
- 概念: 枚舉左子樹的節點數，遞迴生成左右子樹，交叉組合
- 時間複雜度:
O(2^(n/2)) - 空間複雜度:
O(n * 2^(n/2))
class Solution {
fun allPossibleFBT(n: Int): List<TreeNode?> {
if (n % 2 == 0) return emptyList()
if (n == 1) return listOf(TreeNode(0))
val result = mutableListOf<TreeNode?>()
for (leftCount in 1 until n step 2) {
val rightCount = n - 1 - leftCount
val leftTrees = allPossibleFBT(leftCount)
val rightTrees = allPossibleFBT(rightCount)
for (left in leftTrees) {
for (right in rightTrees) {
val root = TreeNode(0)
root.left = left
root.right = right
result.add(root)
}
}
}
return result
}
}⭐ 2: 遞迴 + Memoization#
- 概念: 用 HashMap 快取不同 n 值的結果，避免重複計算
- 時間複雜度:
O(2^(n/2)) - 空間複雜度:
O(n * 2^(n/2))
class Solution {
private val memo = HashMap<Int, List<TreeNode?>>()
fun allPossibleFBT(n: Int): List<TreeNode?> {
if (n % 2 == 0) return emptyList()
if (n == 1) return listOf(TreeNode(0))
memo[n]?.let { return it }
val result = mutableListOf<TreeNode?>()
for (leftCount in 1 until n step 2) {
val rightCount = n - 1 - leftCount
val leftTrees = allPossibleFBT(leftCount)
val rightTrees = allPossibleFBT(rightCount)
for (left in leftTrees) {
for (right in rightTrees) {
val root = TreeNode(0)
root.left = left
root.right = right
result.add(root)
}
}
}
memo[n] = result
return result
}
}🔑 Takeaways#
- Pattern: 與 95 題（Unique BST II）結構相似，都是枚舉分割點 + 遞迴生成 + 交叉組合
- 關鍵技巧: 利用「滿二元樹節點數必為奇數」快速剪枝，步長為 2 減少一半的枚舉