在 Python 中计算具有 n 个节点的 BST 数量的程序

假设我们有 n 个不同的节点。都是不同的。我们必须找出多少种方法可以排列它们以形成二叉搜索树。正如我们对二叉搜索树所知，左子树总是保存较小的值，右子树保存较大的值。

为了解决这个问题，我们将找到加泰罗尼亚数。加泰罗尼亚数C(n)表示具有 n 个不同键的二叉搜索树。公式就像

$$C(n)=\frac{(2n)!}{(n+1)!\times n!}$$

因此，如果输入类似于 n = 3，那么输出将为 5，因为

示例

让我们看看以下实现以更好地理解 -

from math import factorial

def ncr(n, r):
   res = 1
   if r > n - r:
      r = n - r

   for i in range(r):
      res *= (n - i)
      res //= (i + 1)

   return res

def solve(n):
   c = ncr(2 * n, n)
   return c //(n + 1)

n = 3
print(solve(n))

输入

3

5