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

我想写一个方法来找出一棵树是否至少有一对相同的子树，子树的值和结构都必须相同。
假设给你一棵树，如下所示：

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

这将返回true，因为我们有一对根d相同的树。
我的想法是遍历每个节点并构建一个映射到node name列表的tree nodes映射在每次迭代中，我们检查当前节点名是否在映射中如果它在中，那么我们可以对树节点列表中的每个节点调用当前节点的boolean isSameTree(TreeNode t1, TreeNode t2)函数来查看它们是否相同。
时间复杂度为O（n ^ 3）。我想知道我们能不能做得更好！

最佳答案

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