什么是卡特兰数？

卡特兰数是组合数学中一个常出现在各种计数问题中出现的数列。其公式为 :c(n)=c(2)*c(n-1)+c(3)*c(n-2)+...c(n-1)*c(2)。

假设n个节点存在

• 令G(n)的从1到n可以形成二叉排序树个数
• 令f(i)为以i为根的二叉搜索树的个数

即有:G(n) = f(1) + f(2) + f(3) + f(4) + ... + f(n)

n为根节点，当i为根节点时，其左子树节点个数为[1,2,3,...,i-1]，右子树节点个数为[i+1,i+2,...n]，所以当i为根节点时，其左子树节点个数为i-1个，右子树节点为n-i，即f(i) = G(i-1)*G(n-i),

上面两式可得:G(n) = G(0)*G(n-1)+G(1)*(n-2)+...+G(n-1)*G(0)

即：

接下来看几个应用题：

1、不同的二叉搜索树

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

输入: 3
输出: 5
解释:  给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

   1         3     3      2      1
          /     /          /      
     3    2    1        1   3      2
    /     /                              
   2     1         2                    3

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-binary-search-trees/

动态规划：
1、初始化]dp=[0,⋯,0]，长度为n+1，保存n0,⋯,n的卡特兰数。初始化dp[0]=1,表示没有节点, dp[1]=1，表示只有一个节点的二叉搜索树的种类。

2、遍历dp数组，i遍历区间[2,n+1)：

• 计算卡特兰数，j遍历区间[0,i)
• 由卡特兰数公式：dp[i]+=dp[j]*dp[i-j-1]

3、返回dp[n]dp[n]

def generateTrees(n):
if n == 0:
return 0
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
for i in range(2, n + 1):
for j in range(i):
dp[i] += dp[j] * dp[i - j - 1]
return dp[-1]

2、不同的二叉搜索树 II

给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。

输入: 3
输出:
[ [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-binary-search-trees-ii/

二叉搜索树, 一节点大于左子树节点, 小于右子树节点

所以我们节点是从1到n,当一个节点为val那么它的左边是<= val,右边是>=val,

def generateTrees1(n):
if n == 0:
return []
@functools.lru_cache(None)
def dfs(start, end):
res = []
if start > end:
res.append(None)
for val in range(start, end + 1):
for left in dfs(start, val - 1):
for right in dfs(val + 1, end):
root = TreeNode(val)
root.left = left
root.right = right
res.append(root)
return res
return dfs(1, n)

——————————————————————————————

参考：

https://zhuanlan.zhihu.com/p/54928384

最后

以上就是激昂大树为你收集整理的卡特兰数&不同的二叉搜索树什么是卡特兰数？1、不同的二叉搜索树2、不同的二叉搜索树 II的全部内容，希望文章能够帮你解决卡特兰数&不同的二叉搜索树什么是卡特兰数？1、不同的二叉搜索树2、不同的二叉搜索树 II所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。