math - 高度≤H且有N个节点的二叉搜索树的根之和

Question

考虑可以使用前 N 个自然数创建的所有高度 ≤H 的二叉搜索树。求这些二叉搜索树的根之和。

例如，对于 N = 3，H = 3:有 2 棵以 1 为根的树，1 棵以 2 为根的树，以及 2 棵以 3 为根的树。

因此，总和 = 2*(1)+1*(2)+2*(3)=10

我试图通过编写一个函数 f(n,h) 来解决这个问题，该函数以某种方式与 f(n−1,h−1) 和 f(n−1,h) 相关，但无法找到解决方案。

注意:树中必须存在所有数字[1,N]且高度应≤H

Answer 1

好吧，让我们从基础开始。

使用前 N 个自然数可以创建的 BST 数量可以使用以下算法非常容易地计算出来。

natural_number compute_no_of_BST(N)
{
 if(N<=1)
  return 1;
 else
 {
  left=0,right=0,sum=0;
  for(root = 1 to N)
  {
   left = compute_no_of_BST(root-1);
   right =  compute_no_of_BST(N-root);
   sum = sum + (left*right);
  }
  return sum;
 }
}

说明:

理解这个算法的关键是:

无论不同的键是什么，BST的数量只取决于不同的键的数量

因此，这就是我们在递归中使用的。对于左子树，不同值的数量为 root-1，对于右子树，不同值的数量为 N-root。此外，我们为每个键提供成为root 使用 for 循环。

现在，让我们处理高度 H 的约束。我假设高度是从根到叶路径的边数。这也可以通过关注上述算法来解决，技巧是:

我们不会调用高度 > H 的递归函数，为此我们必须跟踪从根遍历的边数，最初为 0。

这样就可以将范围缩小到新函数调用的样子。

natural_number compute_no_of_BST(N,H,0);

每次我们进行递归调用时，我们都会增加第三个变量以指示边缘遍历。

我们还将使用一个额外的数据结构，它是一个长度为 N 的数组，其中

arr[i] = number of BST with root i+1.

这是这个算法

natural_number compute_no_of_BST(N,H,l)
{
 if(N<=1)
  return 1;
 else
 {
  left=0,right=0,sum=0;
  for(root = 1 to N)
  {
   if(l+1<=H)
   {
    left = compute_no_of_BST(root-1,H,l+1);
    right =  compute_no_of_BST(N-root,H,l+1);
    if(l==0)
     arr[root-1] = (left*right);
   sum = sum + (left*right);
   }
  }
  return sum;
 }
}

现在总和可以很容易地计算为

arr[0]*1 + arr[1]*2 + ..... arr[N-1]*N.