【Leetcode】【python】Unique Binary Search Trees II

题目大意

给出一个n，求1-n能够得到的所有二叉搜索树，输出所有树

解题思路

递归拼接树

该题较难，参考题解的思路。

从start到end，先把左右字数的所有可能先迭代出来，之后递归加入左右字数，生成每一颗新树。

代码

class Solution(object):
    def generateTrees(self, n):
        if n == 0:
            return []
        return self.helper(1, n)

    def helper(self, start, end):
        result = []
        if start > end:
            result.append(None)
            return result

        for i in range(start, end + 1):
            # generate left and right sub tree
            leftTree = self.helper(start, i - 1)
            rightTree = self.helper(i + 1, end)
            # link left and right sub tree to root(i)
            for j in range(len(leftTree)):
                for k in range(len(rightTree)):
                    root = TreeNode(i)
                    root.left = leftTree[j]
                    root.right = rightTree[k]
                    result.append(root)

        return result

总结