python - 创建相同 BST 的节点插入序列数？

Question

我有一个与此类似的问题。给定一个产生 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))

如何修改此代码以允许重复键？

标签： pythonbinary-search-treecombinationspermutationcombinatorics

Answer 1

为了允许左子树中的重复键，我只需要更改if a < lst[0]为if a <= lst[0]. 如果有人需要答案，我会留下问题。