检查二叉树是否有两个相同的子树

Question

我想写一个方法来判断一棵树是否至少有一对相同的子树，子树的值和结构都必须相同

假设给你一棵树如下：

        a
       / \
      b   f
     /   / \
    c   g   d
   /   /   /
  d   h   e
 /
e

这会 return true 因为我们有一对相同的树，根 d。

我的想法是遍历每个节点并构建映射到 tree nodes 列表的 node name 的映射。在每次迭代中，我们检查当前节点名称是否在地图中。如果它在，那么我们可以用当前节点对树节点列表中的每个节点调用 boolean isSameTree(TreeNode t1, TreeNode t2) 函数来查看它们是否相同。

时间复杂度为 O(n^3)。我想知道我们是否可以做得更好！

Answer 1

您的示例树也有一对相同的树，根为 e。一般来说，如果两棵树是相同的，那么它们要么都是叶子，要么它们的子树是相同的。因此，您可以简化测试以检查原始树中的所有叶子是否不同，这需要 O(n) 哈希操作和平均情况 Theta(n) 相等性比较，除非哈希非常差。

检查二叉树是否有两个相同的子树

Check if a binary tree has two identical subtrees

algorithm

tree

data-structures