algorithm - 如果叶子从左到右的顺序是固定的，那么有多少二叉树？

Question

让我们通过列表来表示树。

如果叶子的数量是两个，A 和 B。那么只有一棵树 (AB)。

如果叶子的数量是三，A，B和C。那么有两棵树（（AB）C）和（A（BC））。

那么如果有 N 片叶子，那么有多少棵树呢？

Answer 1

N设有叶子的二叉树的数目为T(N)。

可以立即看出，我们有T(1) = T(2) = 1，因为N > 2我们可以在根部进行分裂，从而获得两个叶子较少的子树。N或者，等价地，我们可以从两个非空二叉树中分别组装一棵带有叶子k的二叉树N-k。两个子树都不为空的条件转换为1 <= k <= N-1。所以我们有递归

      N-1
T(N) = ∑  T(k) * T(N-k)
      k=1

如果递归还不知道，计算前几个值并不难

1,1,2,5,14,42,132,429,1430,4862,16796

并谷歌他们。人们发现这些是加泰罗尼亚数字，

C(n) = (2*n)! / (n! * (n+1)!)

偏移一，所以

T(N) = C(N-1)

它的计算速度比递归快得多。