We could base on the discussion above and solve the problem recursivly.
# 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]:
if N == 0:
return []
elif N == 1:
return [TreeNode(0)]
ans = []
for l in range(1, N - 1):
r = N - l - 1
lefts = self.allPossibleFBT(l)
rights = self.allPossibleFBT(r)
for left in lefts:
for right in rights:
node = TreeNode(0)
node.left, node.right = left, right
ans.append(node)
return ans