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

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

<p>A <strong>full binary tree</strong> is a binary tree where each node has exactly <code>0</code> or <code>2</code> children.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://s3-lc-upload.s3.amazonaws.com/uploads/2018/08/22/fivetrees.png" style="width: 700px; height: 400px;" />
<pre>
<strong>Input:</strong> n = 7
<strong>Output:</strong> [[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]]
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 3
<strong>Output:</strong> [[0,0,0]]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 20</code></li>
</ul>

class Solution:
    @cache
    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
        if n==0:
            return []
        mem = {}
        def generate_tree(left, right):
            if left > right:
                return [None]

            if (left,right) in mem: return mem[(left,right)]
            result = []
            for root in range(left, right+1):
                left_tree = generate_tree(left, root-1)
                right_tree = generate_tree( root+1, right)

                for l in left_tree:
                    for r in right_tree:
                        if l==r==None:
                            node = TreeNode(0, l, r)
                            result.append(node)
                            mem[(left,right)] = result
                        elif (l != None) and (r != None):
                            node = TreeNode(0, l, r)
                            result.append(node)
                            mem[(left,right)] = result
            return result
        return generate_tree(1, n)

# class Solution:
#     @cache
#     def allPossibleFullBST(self, start: int, end: int) -> List[Optional[TreeNode]]:
#         if start > end:
#             return [None]

        
#         all_trees = []
#         for i in range(start, end + 1):
#             left_trees = self.allPossibleFullBST(start, i - 1)
#             right_trees = self.allPossibleFullBST(i + 1, end)
            
#             for lt in left_trees:
#                 for rt in right_trees:
#                     if (lt is None) == (rt is None):
#                         current_tree = TreeNode(0, left=lt, right=rt)
#                         all_trees.append(current_tree)
        
#         return all_trees

#     def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
#         if n == 0 or n % 2 == 0:
#             return []
#         return self.allPossibleFullBST(1, n)
23400