LeetCode 96 不同的二叉搜索树

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例 1：

输入：n = 3
输出：5

示例 2：

输入：n = 1
输出：1

提示：

• 1 <= n <= 19

解题：

// 利用昨天的方法偷鸡
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func numTrees(n int) int {
	if n <= 0 {
		return 0
	}
	var dfs func(start, end int) []*TreeNode
	dfs = func(start, end int) []*TreeNode {
		if start > end {
			return []*TreeNode{nil}
		}
		var allTrees []*TreeNode
		for i := start; i <= end; i++ {
			leftTrees := dfs(start, i-1)
			rightTrees := dfs(i+1, end)
			for _, left := range leftTrees {
				for _, right := range rightTrees {
					curTree := &TreeNode{i, left, right}
					allTrees = append(allTrees, curTree)
				}
			}
		}
		return allTrees
	}
	return len(dfs(1, n))
}

结果超时了。。。

官方解答：

1.动态规划

func numTrees(n int) int {
	G := make([]int, n+1)
	G[0], G[1] = 1, 1
	for i := 2; i <= n; i++ {
		for j := 1; j <= i; j++ {
			G[i] += G[j-1] * G[i-j]
		}
	}
	return G[n]
}

2.数学

func numTrees(n int) int {
	C := 1
	for i := 0; i < n; i++ {
		C = C * 2 * (2*i + 1) / (i + 2)
	}
	return C
}