Unique Binary Search Trees II

Problem: Unique Binary Search Tree II

For n numbers, we simply choose random one i as root of Binary Search Tree, and insert all i-1 numbers which are smaller than i into tree's left node and all n-i numbers which are bigger than i into tree's right node. We can do this recursively thus form an depth-first search solution.

Code in Python:

class Solution(object):
    def generateTrees(self, n):
        """
        :type n: int
        :rtype: List[TreeNode]
        """
        if not n:
            return [[]]
        return self.dfs(1, n+1)

    def dfs(self, start, end):
        if start == end:
            return None
        res = []
        for i in xrange(start, end):
            for node1 in self.dfs(start, i) or [None]:
                for node2 in self.dfs(i+1, end) or [None]:
                    node = TreeNode(i)
                    node.left, node.right = node1, node2
                    res.append(node)
        return res