Unique Binary Search Trees II

这道题的解法稍微有点难懂，不过概括起来可以归结为分治法，以1-n中的任意一个数为根节点，同时划分两个子区域再去找结果，最后把子结果中的结果拼起来，这道题对于范围到底是代表区域还是代表结点个数思维很混乱

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

    def generate(self, start, end):
        result = []
        if start > end:
            return result + [None]

        for i in xrange(start, end + 1):
            left = self.generate(start, i - 1)
            right = self.generate(i + 1, end)
            for leftNode in left:
                for rightNode in right:
                    root = TreeNode(i)
                    root.left = leftNode
                    root.right = rightNode
                    result.append(root)

        return result