不同的二叉搜索树

1. 题目描述

给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？

2. 思路

• DFS
  • 如果整数 1 - n 中的 k 作为根节点值，则 1 - k-1 会去构建左子树，k+1 - n 会去构建右子树。
    • 左子树出来的形态有 a 种，右子树出来的形态有 b 种，则整个树的形态有 a * b 种。
• DFS+缓存
• 动态规划

3. 实现

3.1. DFS

func numTrees(n int) int {
    if n <= 1 {
        return 1
    }
    res := 0
    //[1,n]任意一个数作为root，左边子树的个数*右边子树的个数即为答案
    //比如[1,7]，root是3，那么左边是[1,2]，剩下3-1=2个元素。右边是[4,5,6,7]，剩下7-3=4个元素
    for i := 1; i <= n ; i++ {
        res += numTrees(i-1) * numTrees(n-i)
    }
    return res
}

3.2. DFS+缓存

func numTrees(n int) int {
    memo := make(map[int]int, 0)
    return numTreesDFS(n, memo)
}


func numTreesDFS(n int, memo map[int]int) int {
    count, ok := memo[n]
    if ok {
        return count
    }

    if n <= 1 {
        return 1
    }

    count = 0
    for i := 1; i <= n; i++{
        count += numTreesDFS(i-1, memo)*numTreesDFS(n-i, memo)
    }
    memo[n] = count
    return count
}

3.3. 动态规划

package main

func numTrees(n int) int {
	store := []int{1, 1}
	if n <= 1 {
		return store[n]
	}

	for i := 2; i < n+1; i++ {
		s := i-1
		count := 0
		for j := 0; j < i; j++ {
			count += store[j] * store[s-j]
		}
		store = append(store, count)
	}

	return store[n]
}

4. 参考

• 画解算法：96. 不同的二叉搜索树 - 不同的二叉搜索树 - 力扣（LeetCode）
• 【不同的二叉搜索树】递归&动态规划&数学&打表 - 不同的二叉搜索树 - 力扣（LeetCode）