Leetcode 930 Solution

This article provides solution to leetcode question 930 (all-possible-full-binary-trees)
Categories:
Tags:
Access this page by simply typing in "lcs 930" in your browser address bar if you have bunnylol configured.

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

Solution

# 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]:
        self.m = collections.defaultdict(list)

        def dfs(N):
            if N == 0:
                return [None]

            if N in self.m:
                return self.m[N]

            ans = []
            for i in range(N):
                left_trees = dfs(i)
                right_trees = dfs(N - i - 1)

                for left, right in itertools.product(left_trees, right_trees):
                    if (left is None) == (right is None):
                        node = TreeNode(0)
                        node.left = left
                        node.right = right
                        ans.append(node)

            self.m[N] = ans
            return ans

        return dfs(N)