跳至主要內容

0095. 不同的二叉搜索树 II

ITCharge大约 1 分钟

0095. 不同的二叉搜索树 IIopen in new window

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

题目大意

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

解题思路

如果根节点为 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)