All Possible Full Binary Trees LeetCode solution in Python

1
We can't create Full Binary tree with even number of nodes. e.g n = 2/4/6/8...
2
start with cache having n = 1
3
	cache = {1:TreeNode()}
4

5
	n = 3
6
							0 (root)
7
						 1     1
8
	n = 5       
9
	                        0 (root1)                  0 (root2) 
10
						 1     3                     3    1
11
	n = 7  
12
	                         0                    0                   0
13
						 1      5              3    3              5     1
14

15

16
class Solution:
17
    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
18
        def helper(n):
19
            if n in cache:
20
                return cache[n]
21
            # We use result array to store all possible binary tree of size n
22
            result = [] 
23
            leftNodes, rightNodes = 1,n-2
24
            # if n = 7 then, (leftNodes,rightNodes) should be : (1,5),(3,3),(5,1) 
25
            while rightNodes >0:
26
                root = TreeNode()
27
                if leftNodes not in cache:
28
                    helper(leftNodes)
29
                if rightNodes not in cache:
30
                    helper(rightNodes)
31
                leftTree = cache[leftNodes]
32
                rightTree = cache[rightNodes]
33
                # Using two for loops we generate all possible binary tree.
34
                # Always remember root of each binary tree is diffrent, So create new root every time
35
                for i in range(len(leftTree)):
36
                    for j in range(len(rightTree)):
37
                        root.left = leftTree[i]
38
                        root.right = rightTree[j]
39
                        result.append(root)
40
                        root = TreeNode()
41
                leftNodes += 2
42
                rightNodes -= 2
43
            cache[n] = result
44
            return result
45

46
        if n % 2 == 0:
47
            return 
48
        else:
49
            cache = {1:[TreeNode()]}
50
            return helper(n)
51

52
Thank You 😊
53