LeetCode solutions

all-possible-full-binary-trees.py

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def allPossibleFBT(self, N: int) -> List[TreeNode]:
        # ensure N is odd
        if N % 2 == 0:
            return []

        if N == 1:
            return [TreeNode(0)]
        else:
            result = []
            
            # Take a node for the root, and spread the rest from left to right
            # We use a local cache for the sub-trees, since they are symmetrical
            cache = {}
            for i in range(1, N - 1, 2):
                cache[i] = self.allPossibleFBT(i)
            
            for i in range(1, N - 1, 2):
                j = (N - 1) - i
                i_nodes = cache[i]
                j_nodes = cache[j]
                
                for i_node in i_nodes:
                    for j_node in j_nodes:
                        node = TreeNode(0)
                        node.left = i_node
                        node.right = j_node
                        
                        result.append(node)
                
            return result