递归, 对于[start, end]范围内的每个节点, 产生所有可能的左、右子树, 再产生(#左子树 x #右子树)棵树, 返回所有的root nodes。gen函数返回一个list of root nodes, 每个root node所表示的树是由[start, end]这个范围内的数构成的BST。

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @return a list of tree node
    def generateTrees(self, n):
        return self.gen(1, n)

    def gen(self, start, end):
        # return a list containing all root nodes of BSTs constructed from [start, end]
        if start > end: return [None]
        res = []
        for rootVal in xrange(start, end + 1):
            leftList = self.gen(start, rootVal - 1)
            rightList = self.gen(rootVal + 1, end)
            for i in leftList:
                for j in rightList:
                    root = TreeNode(rootVal)
                    root.left = i
                    root.right = j
                    res.append(root)
        return res