⚡Flashcard Drill➔
NeetCode #454LC-894MediumTrees
← Back to All Problems

#454 · #894 · All Possible Full Binary Trees(所有可能的真二叉树)

📌 Problem Statement & Constraints

Given an integer n, return a list of all possible full binary trees with n nodes. A full binary tree has nodes with either 0 or 2 children. Return the roots in any order. Constraints: 1 <= n <= 20.

💡 Core Algorithmic Approaches

  1. A full binary tree always has an odd number of nodes, so an even n returns an empty list.
  2. For a root, the remaining n - 1 nodes split into a left subtree of k and a right subtree of n - 1 - k, where both k and n-1-k are odd.
  3. So iterate k over the odd values and combine every left tree with every right tree.
  4. Memoisation on the node count avoids recomputing the same subtree sets.

💻 Benchmark Python3 Implementation

class Solution:
    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
        if n % 2 == 0:
            return []                      # a full binary tree has odd size
        memo = {1: [TreeNode(0)]}

        def build(k: int) -> List[Optional[TreeNode]]:
            if k in memo:
                return memo[k]
            res = []
            for left_size in range(1, k, 2):    # left subtree sizes are odd
                right_size = k - 1 - left_size
                for l in build(left_size):
                    for r in build(right_size):
                        res.append(TreeNode(0, l, r))
            memo[k] = res
            return res

        return build(n)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(Catalan(n/2) * n): the number of full binary trees with n nodes is a Catalan number.
💾 Space Complexity
O(Catalan(n/2)) for the memoised results.

⚠️ Interview Pitfalls & Follow-ups

  • Not short-circuiting even n: the loop over odd sizes would simply produce nothing, but the explicit guard is clearer.
  • Iterating left_size over all values: both subtree sizes must be odd, so the step must be 2 starting from 1.
  • Recomputing build for the same size: exponential without memoisation.
  • Trying to deduplicate trees: every combination is structurally distinct, so no deduplication is needed.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Trees Problems