У меня похожая проблема с этой .Учитывая определенную последовательность вставки, которая производит 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))
Как я могу изменить этот код, чтобы разрешить дублирование ключей?