节点插入序列，其创建相同的BST的号码？

Question

我有一个类似的问题this one。鉴于其产生的BST一定插入序列，我需要计数许多插入序列（包括给出的一种）如何产生相同的BST。

主要的区别是，我的解决方案需要允许重复键（我只能找到解决方案，其中所有的键必须是不同的）。正是在这种键等于当前的关键始终走在左子树（与一些不太钥匙一起）的问题指定。

到目前为止我的代码（在很大程度上受到连接问题，这似乎工作，其中关键是不同的接受的答案启发）：

def num_orders(lst):
    if len(lst) <= 1:
        return 1
    num_remaining = len(lst)-1
    left_subtree = []
    right_subtree = []
    for a in lst[1:]:
        if a < lst[0]:
            left_subtree.append(a)
        if a > lst[0]:
            right_subtree.append(a)
    return num_orders(left_subtree)*num_orders(right_subtree)*nCr(num_remaining,len(left_subtree))

我怎么能修改此代码，允许重复键？

Answer 1

为了让在左子树重复键，我只需要改变if a < lst[0]到if a <= lst[0]。我将离开这个问题了，以防有人需要的答案。