algorithm - 作为树高的函数，可能的二叉树的数量之间是否存在联系？

Question

处理平衡和不平衡的二叉树。

height = 0, possible trees = 1 (nothing)
height = 1, possible trees = 1 (leaf)
height = 2, possible trees = 3

我正在研究加泰罗尼亚函数，但它并没有给我带来任何好处，主要是因为我认为它可能会计算小于高度 h 的树木。例如，如果高度为 2，我相信它也会计算高度 1（也许高度为 0）。

Answer 1

您似乎正在寻找整数序列A001699，“高度为 n 的二叉树数”。生成它们的一种可能算法是：

a(n+1) = 2*a(n)*(a(0)+...+a(n-1))+a(n)^2

不幸的是，似乎没有封闭形式的版本。每个公式本身都是递归的，或者使用 A003095，它也是递归的。