96. 不同的二叉搜索树

95. 不同的二叉搜索树 II

给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。

image.png

复杂度分析

  • 时间复杂度 : O(n_2)，其中 n_n 表示二叉搜索树的节点个数。G(n) 函数一共有 n个值需要求解，每次求解需要 O(n) 的时间复杂度，因此总时间复杂度为 O(n^2)。

  • 空间复杂度 : O(n)。我们需要 O(n) 的空间存储 G数组。

    1. //动态规划法，
    2. func numTrees(n int) int {
    3.   dp := make([]int, n + 1)
    4.   dp[0], dp[1] = 1, 1
    6.   for i := 2; i <= n; i++ {
    7.       for j := 1; j <= i; j++ {
    8.           dp[i] += dp[j-1] * dp[i-j]
    9.       }
    10.   }
    12.   return dp[n]
    13. }

image.png

//数学法，通项公式
func numTrees(n int) int {
    C := 1
    for i := 0; i < n; i++ {
        C = C * 2 * (2 * i + 1) / (i + 2);
    }
    return C
}

问题二：构建一颗二叉搜索树

image.png

//递归+回溯
func generateTrees(n int) []*TreeNode {
    if n == 0 {
        return []*TreeNode{}
    }
    return dfs_tree(1,n)    // 核心三：递归生成从[start,end]区间范围内的树
}

func dfs_tree(start, end int) []*TreeNode {
    if start > end {
        return []*TreeNode{nil}     //这里 是 递归的终点，所以要用类型，然后加nil 初始化
    }

    //尝试每个数字作为根节点，i节点为根节点时，左子树i-1个节点，右子树n-i个节点
    res_Trees := []*TreeNode{}      //把第二层的子树，一个个加起来

    // 核心一：以i为根节点，生成左右子节点
    for i := start; i <= end ; i++ {
        left_tree := dfs_tree(start, i-1)
        right_tree := dfs_tree(i+1, end)

        // 核心二：拼接所有的树
        for _, left := range left_tree {
            for _, right := range right_tree {
                //res_Trees = append(res_Trees, &TreeNode{i, tree, tree})
                root := &TreeNode { Val: i,}
                root.Left = left
                root.Right = right
                res_Trees = append(res_Trees, root)
            }
        }
    }
    return res_Trees
}