All Possible Full Binary Trees

Given an integer n, return a list of all possible full binary trees with n nodes. Each node of each tree in the answer must have Node.val == 0.

Each element of the answer is the root node of one possible tree. You may return the final list of trees in any order.

A full binary tree is a binary tree where each node has exactly 0 or 2 children.

Example 1:

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]]

Example 2:

Input: n = 3
Output: [[0,0,0]]

Constraints:

• 1 <= n <= 20

SOLUTION:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def getTrees(self, n: int) -> List[Optional[TreeNode]]:
        trees = []
        if n == 1:
            return [TreeNode()]
        if n in self.cache:
            return self.cache[n]
        for i in range(1, n, 2):
            lefts = self.getTrees(i)
            rights = self.getTrees(n - i - 1)
            for left in lefts:
                for right in rights:
                    root = TreeNode()
                    root.left = left
                    root.right = right
                    trees.append(root)
        self.cache[n] = trees
        return trees

    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
        self.cache = {}
        return self.getTrees(n)