algorithm - 查找产生相同二叉搜索树的给定整数序列的排列数

Question

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

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

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

Answer 1

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

例如，对于 BST

  10
 /  \
5   20
 \7 | \
    15 30

拓扑排序集可以这样手工计数:10 开始每个排序。以 20 开头的子树的拓扑排序数为两个:(20, 15, 30) 和 (20, 30, 15)。以 5 开头的子树只有一种排序:(5, 7)。这两个序列可以以任意方式交错，导致 2 x 10 交错，从而产生产生相同 BST 的 20 个输入。下面列举前 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 中的所有节点都具有不同的 key 。