algorithm - 如何在给定的两个二叉搜索树中找到最大的公共(public)子树？

Question

给出了两个BST(二叉搜索树)。如何在给定的两个二叉树中找到最大的公共(public)子树？

编辑 1: 这是我的想法:

设，r1 = 第一棵树的当前节点 r2 = 第二棵树的当前节点

There are some of the cases I think we need to consider:

Case 1 : r1.data < r2.data
     2 subproblems to solve:
     first, check r1 and r2.left 
     second, check r1.right and r2

Case 2 : r1.data > r2.data
     2 subproblems to solve:
       - first, check r1.left and r2
       - second, check r1 and r2.right

Case 3 : r1.data == r2.data
     Again, 2 cases to consider here:
     (a) current node is part of largest common BST
         compute common subtree size rooted at r1 and r2
     (b)current node is NOT part of largest common BST
         2 subproblems to solve:
         first, solve r1.left and r2.left 
         second, solve r1.right and r2.right

我能想到我们需要检查的情况，但我现在无法编写代码。这不是作业问题。看起来像吗？

Answer 1

只需散列每个节点的子节点和键并查找重复项。这将给出线性预期时间算法。例如，请参见以下伪代码，它假定不存在哈希冲突(处理冲突会很简单):

ret = -1
// T is a tree node, H is a hash set, and first is a boolean flag
hashTree(T, H, first):
  if (T is null):
    return 0 // leaf case
  h = hash(hashTree(T.left, H, first), hashTree(T.right, H, first), T.key)
  if (first):
    // store hashes of T1's nodes in the set H
    H.insert(h)
  else:
    // check for hashes of T2's nodes in the set H containing T1's nodes
    if H.contains(h):
      ret = max(ret, size(T)) // size is recursive and memoized to get O(n) total time
  return h

H = {}
hashTree(T1, H, true)
hashTree(T2, H, false)
return ret

请注意，这是假设 BST 子树的标准定义，即子树由一个节点及其所有后代组成。