查找给定整数序列的排列数，这些排列产生相同的二叉搜索树

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

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

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

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

例如，对于 BST

  10
 /  \
5   20
 \7 | \
    15 30

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

 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 中的所有节点都有不同的密钥。