Problem statement

https://leetcode.com/problems/all-possible-full-binary-trees/

Solution

Let trees[k] be all full binary trees with k nodes. Then these trees can be constructed, using tree with i nodes for left child and with k-i-1 nodes for right child. Note also, that only for odd n there exist full binary tree with n nodes.

Complexity

Time complexity is $C_{(n-1)/2}\cdot n$ ($C_i$ is Catalan number), because it can be show that this number of trees exist. Space complexity is the same.

Code

class Solution:
    def allPossibleFBT(self, n):
        trees = [[] for _ in range(n+1)]
        trees[1] = [TreeNode()]
        
        for k in range(n+1):  
            for i in range(1, k-1, 2):
                for left in trees[i]:
                    for right in trees[k - i - 1]:
                        root = TreeNode()
                        root.left = left
                        root.right = right
                        trees[k].append(root)
                        
        return trees[-1]