2

如果两棵树包含相同的元素集但可能具有不同的结构，则称它们是相同的。例如 4,3,5 和 5,4,3

如何检查两棵树是否相同？

我能想到的一种方法是使用散列。对于第一棵树中的每个元素，相应的计数都会增加。对于第二棵树中的每个元素，计数都会递减。最后，哈希为空，我们确定树是相同的。时间复杂度：O(N) 空间复杂度：O(N)

但是，这种方法没有利用树是 BST 还是简单的二叉树。

方法2：对数组中的两棵树进行中序遍历。我们有两个具有排序数据的数组。进行线性搜索以检查数组是否相同。时间复杂度：O(N) 空间复杂度：O(N)

但是，我想知道是否存在更好的解决方案？

4

3 回答 3

6

这回答了最初措辞的问题，即在相同结构和元素的意义上树的身份之后。

比较按顺序（或任何其他）顺序将不起作用：不同的树具有相同的遍历。例如，树木

在此处输入图像描述
[来源]

有相同的中序遍历a,b,c,d,e。您可以使用两个（不同的）遍历并分别检查它们是否相同。

然而，经典的解决方案是递归算法：

  equal Leaf(x)       Leaf(y)       => x == y
| equal Node(x,l1,r1) Node(y,l2,r2) => x == y && equal(l1,l2) && equal(r1,r2)
| equal _             _             => false;

它同时在两棵树上执行树遍历，并花费时间 Θ(n)，n 是各自节点数的最大值。

关于更新的问题，检查按元素相等的顺序遍历就足够了。请注意，根据定义，BST 的中序遍历是存储元素的排序列表，因此这种方法是正确的。以递归形式，这是算法：

  inorder Leaf(x)     = [x]
| inorder Node(x,l,r) = (inorder l) ++ [x] ++ (inorder r);

  equal []     []     = true
| equal x1::r1 x2::r2 = x1 == x2 && (equal r1 r2)
| equal _      _      = false;

  sameElems t1 t2 = let 
                      e1 = inorder t1
                      e2 = inorder t2
                    in
                      equal e1 e2
                    end;

如果列表连接可以在时间 O(1) 内完成，则在时间 Θ(n) 和空间 Θ(n) 中运行；迭代解决方案当然同样好，并且可能具有更好的常数。

如果您想在 o(n) 时间内执行此检查，您甚至无法查看每个元素。一般来说，两棵树都包含成对的不同元素，因此您不能利用任何范围，因此我每个一般的元素相等检查都需要时间 Ω(n)（假设一个更快的算法并构造两棵它失败的树）。

不过，空间可以做得比 O(n) 更好。如果您巧妙地按顺序实现¹，您只需要 O(1) 额外空间（指向当前元素的指针，一些管理计数器/标志）。

  1. 请注意，此算法会暂时破坏树，因此不适合并发设置。
于 2012-06-08T20:00:07.917 回答
1

散列的问题是，如果你有两个二叉搜索树，{2, 1, 3}并且{0, 0, 6}它们可以有相同的总散列码，你仍然有不同的元素。

顺序遍历方法可能是最有效的方法，而且我怀疑这O(n)是您可以得到的最好的方法n，因为您需要进行相等比较。

于 2012-06-08T15:50:15.387 回答
1

您的后一种解决方案似乎比您的前一种更好，因为后者的最坏情况时间是 O(N)，最好的情况（有序遍历中的第一个元素不同）将是 Ω(1)，而对于前者的最佳情况时间仍然是 Ω(N)，因为您必须等到最后才能确定。

但是，作为对后者的优化，您不能只使用指向每棵树中当前元素的指针而不是复制所有数据吗？用于按顺序遍历树的算法（至少具有自然排序）不需要制作任何数据副本。这样你的空间复杂度将是 O(1)。

于 2012-06-08T15:52:30.433 回答