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

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

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

如果叶子的数量是三个，A、B 和 C。那么有两棵树 ((A B) C) 和 (A (B C))。

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

最佳答案

设 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

并谷歌他们。人们发现这些是 Catalan numbers ，

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

抵消一，所以

T(N) = C(N-1)

这可以比递归计算得快得多。

关于algorithm - 如果叶子从左到右的顺序是固定的，那么有多少棵二叉树？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/14102465/