计算产生相同 BST 的唯一节点序列的数量

问题：

给定一个最多 50 个整数的特定序列，它们代表 某个二叉搜索树（BST）的节点，有多少种排列 这个序列在那里，这也会产生完全相同的 空白石板时间？将原始序列作为 1 个序列包含在总计数中。

例如，对于这样的序列 [5,2,1,9,8]，答案 = 6：[5,2,1,9,8] （本身，给定的原始序列），[5,9,8,2,1]，[5,2,9,1,8]， [5,9,2,1,8], [5,2,9,8,1], [5,9,2,8,1]

假设您有示例序列[5,2,1,9,8]。第一个节点将成为二叉树的根，因此我们知道第一个节点必须是 5。

从那时起，所有小于 5 的节点都将转到左子节点，所有大于 5 的节点将转到右子节点。

所以你可以解决这个问题递归地，计算左子树的生成方式的数量（由[2,1]) 乘以生成右子树的方法数（包括[9,8]) and 乘以对相对两侧的整数到达进行排序的方式数量。

示例代码

def nCr(n,r):
   """Return number of ways of choosing r objects from n"""

   top, bottom = 1, 1
   for i in xrange(r):
      top *= n
      n = n - 1
      bottom *= r
      r = r- 1
   return top / bottom

def count_ways_to_make_bst(seq):
    if len(seq)<=1:
        return 1
    num_remaining = len(seq) - 1
    left = [r for r in seq[1:] if r>seq[0]]
    right = [r for r in seq[1:] if r<seq[0]]
    return count_ways_to_make_bst(left) * count_ways_to_make_bst(right) * nCr(num_remaining,len(left))