树上的高效平等函数

Question

几天前，我收到了以下面试问题。它是用标准 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 f n = 
  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

但我觉得这是一个尴尬的黑客行为，而且显然不是面试官想要的。我怀疑有一种优雅的方法可以避免重新计算子树——它是什么？

Answer 1

从外观上看，您的解决方案是 O(n^2) 。我们可以通过对单个树而不是一对树的身份使用记忆化来使其 O(n)：

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)