相同的BST

Question

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

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

我能想到的一种方法是使用散列.对于第一个树中的每个元素,相应的计数递增.对于第二个树中的每个元素,计数递减.最后,哈希是空的,我们确信树是相同的.时间复杂度:O(N)空间复杂度:O(N)

但是,这种方法没有利用树是BST还是简单的BINARY TREE.

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

但是,我想知道有没有更好的解决方案？

Answer 1

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

比较有序(或任何其他)顺序化将不起作用:不同的树具有相同的遍历.例如,树木

^{[ 来源 ]}

具有相同的有序遍历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. 请注意,此算法会暂时销毁树,因此不适合并发设置.