0095. 不同的二叉搜索树 II

• 标签：树、二叉搜索树、动态规划、回溯、二叉树
• 难度：中等

题目大意

给定一个整数 n，请返回以 1 到 n 为节点构成的「二叉搜索树」，可以按任意顺序返回答案。

解题思路

如果根节点为 i，则左子树的节点为 (1, 2, ..., i - 1)，右子树的节点为 (i + 1, i + 2, ..., n)。可以递归的构建二叉树。

定义递归函数 generateTrees(start, end)，表示生成 [left, ..., right] 构成的所有可能的二叉搜索树。

• 如果 start > end，返回 [None]。
• 初始化存放所有可能二叉搜索树的数组。
• 遍历 [left, ..., right] 的每一个节点 i，将其作为根节点。
  • 递归构建左右子树。
  • 将所有符合要求的左右子树组合起来，将其加入到存放二叉搜索树的数组中。
• 返回存放二叉搜索树的数组。

代码

class Solution:
    def generateTrees(self, n: int) -> List[TreeNode]:
        if n == 0:
            return []

        def generateTrees(start, end):
            if start > end:
                return [None]
            trees = []
            for i in range(start, end+1):
                left_trees = generateTrees(start, i - 1)
                right_trees = generateTrees(i + 1, end)
                for left_tree in left_trees:
                    for right_tree in right_trees:
                        curr_tree = TreeNode(i)
                        curr_tree.left = left_tree
                        curr_tree.right = right_tree
                        trees.append(curr_tree)
            return trees
        return generateTrees(1, n)