目录

0096:不同的二叉搜索树(★)

力扣第 96 题

题目

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

示例 1:

输入:n = 3
输出:5

示例 2:

输入:n = 1
输出:1

提示:

  • 1 <= n <= 19

相似问题:

分析

0095 变型,本题只需要计算数量,可以用 dp。

解答

1
2
3
4
5
6
class Solution:
    def numTrees(self, n: int) -> int:
        dp = [1]*(n+1)
        for i in range(1,n+1):
            dp[i] = sum(dp[j-1]*dp[i-j] for j in range(1,i+1))
        return dp[-1]

29 ms

*附加

这个递推式得到的 dp[n] 在数学上被称为卡塔兰数,有个更简单的表达式:

$$dp[n] = {(2n)! \over (n!*(n+1)!)} $$

1
2
3
class Solution:
    def numTrees(self, n: int) -> int:
        return comb(2*n,n)//(n+1)

37 ms