10

给定一个整数数组arr = [5, 6, 1]。当我们用这个输入以相同的顺序构造一个 BST 时，我们将“5”作为根，“6”作为右孩子，“1”作为左孩子。

现在，如果我们的输入更改为 [5,1,6]，我们的 BST 结构仍然是相同的。

那么给定一个整数数组，如何找到输入数组的不同排列的数量，从而产生与原始数组顺序上形成的 BST 相同的 BST？

4

4 回答 4

13

您的问题相当于计算给定 BST 的拓扑排序数的问题。

例如，对于 BST

  10
 /  \
5   20
 \7 | \
    15 30

可以像这样手动计算拓扑排序集：每个排序有 10 个开始。从 20 开始的子树的拓扑排序数为两个：(20, 15, 30) 和 (20, 30, 15)。以 5 开头的子树只有一个顺序：(5, 7)。这两个序列可以以任意方式交织，导致 2 x 10 次交织，从而产生 20 个产生相同 BST 的输入。下面列举了前 10 个案例 (20, 15, 30)：

 10 5 7 20 15 30
 10 5 20 7 15 30
 10 5 20 15 7 30
 10 5 20 15 30 7
 10 20 5 7 15 30
 10 20 5 15 7 30
 10 20 5 15 30 7
 10 20 15 5 7 30
 10 20 15 5 30 7
 10 20 15 30 5 7

情况 (20, 30, 15) 是类似的——您可以检查以下任何一个输入是否产生相同的 BST。

这个例子还提供了一个递归规则来计算排序的数量。对于叶子，数量为 1。对于具有一个子节点的非叶子节点，该数量等于子节点的拓扑排序数。对于具有两个子树大小为 |L| 的子节点的非叶节点 和 |R|，分别具有 l 和 r 排序，数量等于

  l x r x INT(|L|, |R|)

其中 INT 是 |L| 的可能交错数 和 |R| 元素。这可以通过 (|L| + |R|) 轻松计算！/ (|L|!x |R|!)。对于上面的示例，我们得到以下递归计算：

  Ord(15) = 1
  Ord(30) = 1
  Ord(20) = 1 x 1 x INT(1, 1) = 2  ; INT(1, 1) = 2! / 1 = 2
  Ord(7) = 1
  Ord(5) = 1
  Ord(10) = 1 x 2 x INT(2, 3) = 2 x 5! / (2! x 3!) = 2 x 120 / 12 = 2 x 10 = 20

这解决了问题。

注意：此解决方案假设 BST 中的所有节点都有不同的密钥。

于 2009-11-10T17:34:48.860 回答
1

感谢antti.huima的解释！这有助于我理解。这是一些C++：

#include <vector>
#include <iostream>

using namespace std;

int factorial(int x) {
  return (x <= 1) ? 1 : x * factorial(x - 1);
}

int f(int a, int b) {
  return factorial(a + b) / (factorial(a) * factorial(b));
}

template <typename T>
int n(vector<T>& P) {
  if (P.size() <= 1) return 1;
  vector<T> L, R;
  for (int i = 1; i < P.size(); i++) {
    if (P[i] < P[0])
      L.push_back(P[i]);
    else
      R.push_back(P[i]);
  }
  return n(L) * n(R) * f(L.size(), R.size());
}

int main(int argc, char *argv[]) {
  vector<int> a = { 10, 5, 7, 20, 15, 30 };
  cout << n(a) << endl;
  return 0;
}
于 2013-03-06T02:59:58.710 回答
0

如果您对递归、排列和组合知之甚少，并且熟悉二叉搜索树（显然），这个问题可以很容易地解决。

首先，您使用给定的序列构建二叉搜索树。您也可以在数组中执行相同的操作，但树形可视化会描绘出一幅好的画面。

对于给定的序列 arr[1..n]，第一个元素将保持原样在给定数组中，并且只需要在 arr[2..n] 中引入排列。

认为：

bag1 = arr[2..n] 中小于 arr[0] 的元素数。

和，

bag2 = arr[2..n] 中大于 arr[0] 的元素数。

由于序列中 bag1 中元素的排列不会与 bag2 中存在的数字在形成二叉搜索树时产生冲突，因此可以通过从 (n-1) 个元素中挑选 bag1 元素来开始计算答案permutate and then rest ((n-1) - bag1) = bag2 元素现在只能以 1 种方式放置。bag1 中元素的顺序应该相同，并且对于序列中的 bag2 元素也是如此。

因为二叉搜索树的每个子树都必须是 BST。类似的过程将在每个节点上运行，并将节点的本地答案乘以最终答案。

int ans = 1;
int size[1000000] = {0};

// calculate the size of tree and its subtrees before running function "fun" given below.
int calSize(struct node* root){
     if(root == NULL)
          return 0;

     int l = calSize(root->left);
     int r = calSize(root -> right);
     size[root->val] = l+r+1;
     return size[root->val]; 
}

void fun(struct node* root){
     if(root == NULL)
         return;

     int n = size[root->val];
     if(root->left){
         ans *= nCr(n-1, size[root->left]);
         ans *= 1; // (Just to understand that there is now only 1 way 
                   //to distribute the rest (n-1)-size of root->left)
     }

     fun(root->left);
     fun(root->right); 
}

int main(){
     struct node* root;

     //construct tree
     //and send the root to function "fun"

     fun(root);

     cout<<ans<<endl;
     return 0;
}
于 2017-08-12T08:52:41.907 回答
-1

你可以倒过来做：给定一个 BST，枚举所有可以产生这个 BST 的整数数组......

你不能（使用不确定性......）

  1. 发出根并将其添加到发出的集合中。
  2. 不确定地从树中选择一个不在发射集中但其父项在发射集中的项目，并将其添加到发射集中并发射它。
  3. 重复 2 直到全部发射。

非确定性会给你所有这样的数组。然后你可以数一数。

于 2009-11-09T15:15:56.107 回答