MediumRating 1784

894. All Possible Full Binary Trees

dynamic-programmingtreerecursionmemoizationbinary-tree

在 LeetCode 上作答 ↗

解題說明

All Possible Full Binary Trees

題目描述：給定整數 n，返回所有包含 n 個節點的滿二元樹（Full Binary Tree）。滿二元樹的定義是：每個節點要麼有 0 個子節點（葉子），要麼有 2 個子節點。節點值皆為 0。

解題思路： 遞迴 + 記憶化：

滿二元樹的節點數必為奇數（每次增加一對子節點），若 n 為偶數直接返回空。
基礎情況：n = 1 時返回一個單節點樹。
對 n 個節點的樹，根節點佔 1 個，剩餘 n - 1 個分配給左右子樹。左子樹用 i 個節點，右子樹用 n - 1 - i 個（i 為奇數）。
遞迴生成所有左子樹和右子樹的組合，形成笛卡爾積。
使用 memo 避免重複計算相同的 n。

C++ 解法

複雜度分析

時間複雜度：O(2^(n/2)) — 滿二元樹的數量等於卡特蘭數 C(n/2)，生成每棵樹需 O(n)，總計為 O(n * C(n/2))。

空間複雜度：O(n * 2^(n/2)) — 存儲所有生成的樹節點，加上遞迴棧深度 O(n)。

虛擬碼

1. If n is even, return empty list.
2. If n == 1, return list containing a single node.
3. If memo contains n, return memo[n].
4. Initialize result list.
5. For i = 1, 3, 5, ..., n-2:
   a. leftTrees = allPossibleFBT(i)
   b. rightTrees = allPossibleFBT(n - 1 - i)
   c. For each (left, right) pair: create root with left and right children, add to result.
6. Store result in memo[n] and return.

其他解法

迭代式 DP：用陣列 dp[i] 存放 i 個節點的所有滿二元樹，從小到大構建。與遞迴邏輯相同但避免了棧開銷。空間複雜度不變。

Clone-based 遞迴：每次組合時深拷貝子樹節點，確保不同樹之間不共享節點。記憶體消耗更大，但樹結構獨立，方便後續修改。

延伸思考

滿二元樹的數量與卡特蘭數有什麼關係？能否推導出 n 個節點的滿二元樹數量公式？
如果不使用記憶化，重複計算會導致多少額外開銷？
如何修改此演算法以生成所有 n 個節點的完全二元樹（Complete Binary Tree）？

All Possible Full Binary Trees — CaffeCode