Эффективная функция равенства на деревьях

Несколько дней назад мне дали следующий вопрос интервью. Он был описан со стандартным кодом ML, но я был вправе отвечать на языке по своему выбору (я выбрал Python):

У меня есть тип:

datatype t = Leaf of int | Node of (t * t) 

и функция f с сигнатурой

 val f: int -> t 

Вам нужно написать функцию равную, которая проверяет, equals ли два дерева. f – O(n) , и это «наихудшая возможная вещь» для временной сложности вашей функции equals . Записать equals , чтобы он никогда не экспоненциально по n , аргумент f .

Пример f который был предоставлен:

 fun fn = if n = 0 then Leaf(0) else let val subtree = f (n - 1) in Node (subtree, subtree) end 

который создает экспоненциально большое дерево в O(n) времени, поэтому equals (f(n), f(n)) для наивной equals реализации, линейной по числу узлов дерева является O(2^n) .

Я произвел что-то вроде этого:

 class Node: def __init__(self, left, right): self.left = left self.right = right class Leaf: def __init__(self, value): self.value = value def equals(left, right): if left is right: return True try: return left.value == right.value except ValueError: pass try: return equals(left.left, right.left) and equals(left.right, right.right) except ValueError: return False 

который работал на примере f , предоставленном интервьюером, но не прошел в общем случае « f делает худшее возможное». Он привел пример, который я не помню, что прервала мою первую попытку. Я немного окунулся и в итоге сделал что-то похожее на это:

 cache = {} def equals(left, right): try: return cache[(left, right)] except KeyError: pass result = False try: result = left.value == right.value except ValueError: pass try: left_result = equals(left.left, right.left) right_result = equals(left.right, right.right) cache[(left.left, right.left)] = left_result cache[(left.right, right.right)] = right_result result = left_result and right_result except ValueError: pass cache[(left, right)] = result return result 

но я чувствовал, что это был неуклюжий хак, и это явно не то, что искал интервьюер. Я подозреваю, что есть элегантный способ избежать перекомпоновки поддеревьев – что это?

• Алгоритм поиска подмножества из списка, который выполняет ограничение
• Вычислить STD вручную с помощью Groupby Pandas DataFrame
• Как сделать цветопередачу из цветовой палитры
• алгоритм сжатия группы (пары строк)
• Создание всех 5 карточных покерных рук

 memoByVal = {} memoByRef = {id(None): 0} nextId = 1 # produce an integer that represents the tree's content def getTreeId(tree): if id(tree) in memoByRef: return memoByRef[id(tree)] # nodes are represented by the (left, right, value) combination # let's assume that leafs just have left == right == None l, r = getTreeId(tree.left), getTreeId(tree.right) if (l, r, tree.value) not in memoByVal: memoByVal[l, r, tree.value] = nextId nextId += 1 res = memoByVal[l, r, tree.value] memoByRef[id(tree)] = res return res # this is now trivial def equals(a, b): return getTreeId(a) == getTreeId(b)