题目

给定一个整数 n，生成所有由 1 … n 为节点所组成的二叉搜索树。

示例：

输入: 3
输出:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
解释:
以上的输出对应以下 5 种不同结构的二叉搜索树：
   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

递归

算法实现

def generateTrees(self, n):
    """
    :type n: int
    :rtype: List[TreeNode]
    """
    # 如果 为空树
    if not n:
        return []
    def new_trees(start, end):
        if start > end:
            return [None]
        all_trees = []
        # 针对(start,end)中的每一个i进行切分，也就是求G(i),判断左右是否有节点，通过start和end比较
        for i in range(start, end + 1):
            # 左子树
            left_trees = new_trees(start, i - 1)
            # 右子树
            right_trees = new_trees(i + 1, end)
            for left in left_trees:
                for right in right_trees:
                    tree = TreeNode(i)
                    tree.left = left
                    tree.right = right
                    all_trees.append(tree)
        # print(all_trees)
        # 注：每次递归进入的子树的all_trees都是不一样的。可以通过打印print()查看控制台的输出，这样更容易理解具体的思路。
        return all_trees
    return new_trees(1, n)

执行结果

执行结果 : 通过
执行用时 : 52 ms, 在所有 Python3 提交中击败了87.26%的用户
内存消耗 : 15 MB, 在所有 Python3 提交中击败了8.17%的用户
在这里插入图片描述

复杂度分析

在这里插入图片描述

动态规划

算法实现

def generateTrees(self, n: int):
    if n == 0:
        return []
    # 对dp进行初始化
    dp = []
    for i in range(0, n + 1):  # 初始化dp
        dp.append([])
        for j in range(0, n + 1):
            if i == j:
                dp[i].append([TreeNode(i)])
            elif i < j:
                dp[i].append([])
            else:
                dp[i].append([None])
    dp[0][0] = [None]
    for i in range(n - 1, 0, -1):  # 自下向上进行循环
        for j in range(i + 1, n + 1):
            for r in range(i, j + 1):  # i-j每一个节点为顶点的情况
                left = r + 1 if r < j else r  # 右边的值需要边界判断，不然会溢出数组
                for x in dp[i][r - 1]:  # 左右子树排列组合
                    for y in dp[left][j]:
                        node = TreeNode(r)
                        node.left = x
                        node.right = y
                        if r == j:
                            node.right = None
                        dp[i][j].append(node)  # dp[i][j]添加此次循环的值
    return dp[1][n]