algorithm - 查找给定 n 个键的二叉树数量的变体

Question

给定 n 个不同键的列表 A，可以形成多少个二叉搜索树，使得在任意一棵子树，其左右子树节点数之差为最多一个？

无条件的二叉搜索树个数的递推关系为

f(1) = f(0) = 1;
Let total_trees = 0;
for(int i = 1; i<= n; ++i)
   total_trees += f(i-1) * f(n-i)

谁能帮忙修改一下？

我的尝试(这是错误的):

f(1) = f(0) = 1;
Let total_trees = 0;
for(int i = 1; i<= n; ++i)
   total_trees += f(i) * f(i-1)

Answer 1

让我们所有的键都在线性阵列中。如果键数是偶数，则您有 2 个根变体 - 2 个中心元素。对于奇数个键，只有一个以中心元素为根的变体满足条件。所以递归看起来像:

f(1) = f(0) = 1

f(2*k) = f(k-1) * f(k+1) + f(k+1) * f(k-1) = 2 * f(k-1) * f(k +1)

f(2*k+1) = f(k)*f(k)