Unique Binary Search Trees II

Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1...n.

For example, Given n = 3, your program should return all 5 unique BST's shown below.

1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3

URL: https://leetcode.com/problems/unique-binary-search-trees-ii/

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

class Solution(object):
    def generateTrees(self, n):
        """
        :type n: int
        :rtype: List[TreeNode]
        """
        if n == 0:
            return []
        else:
            return self.tree_constructor(1, n)

    def tree_constructor(self, m, n):
        results = []
        if m > n:
            results.append(None)
            return results

        for i in range(m, n+1):
            l = self.tree_constructor(m, i-1)
            r = self.tree_constructor(i+1, n)
            for left_trees in l:
                for right_trees in r:
                    curr_node = TreeNode(i)
                    curr_node.left = left_trees
                    curr_node.right = right_trees
                    results.append(curr_node)


        return results