问查找两个二进制搜索树的公共元素的最佳方法

EN

假设你的两棵树分别是m和n。您建议的解决方案在timeΘ(n log(m))中工作(或者相反)。您实际上可以在时间Θ(m + n)中这样做。

让我们从一个相关的问题开始。假设您有两个大小分别为m和n的列表，每个列表都进行了排序。您可以很容易地在Θ(m + n)中找到公共元素的数量。只需放置两个“指针”，每个列表一个。通过比较这两个项，您可以确定是增加第一个指针、第二个指针，还是同时增加两个指针(最后一个情况是找到相同的元素时)。(编辑--您可以在this question的答案中看到这一点。)

BST的顺序遍历在概念上与对排序链接列表的遍历相同，因此您可以在这里进行相同的遍历。

您可以对一个BST进行遍历(前、内或后序)，并将节点的值存储在哈希表中。然后遍历另一棵树，并为遇到的每个节点在哈希表中增加相应的值。哈希表中值大于1的任何值都是与两个二进制搜索树相同的值。