[LeetCode] 894. All Possible Full Binary Trees

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

A full binary tree must have odd number of nodes.  So we can find all possible left and right sub trees to construct the needed trees.

# 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:
    @cache
    def allPossibleFBT(self, n: int) -> List[TreeNode]:
        if n == 1:
            return [TreeNode()]
        
        result = []
        
        for i in range(1, n+1):
            left = i - 1
            right = n - i
            
            if left % 2 == 1 and right % 2 == 1:
                lts = self.allPossibleFBT(left)
                rts = self.allPossibleFBT(right)
                
                for lt in lts:
                    for rt in rts:
                        result.append(TreeNode(left=lt, right=rt))
        
        return result