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

Question

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

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

我正在查看 Catalan 函数，但它并没有给我带来任何好处，主要是因为我认为它可能会计算高度小于 h 的树。例如，如果高度为 2，我相信它也会计算高度 1(也可能是高度 0)。

Answer 1

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

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

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