我正在寻找一种顺序算法(如果存在的话)来测试两个 BST 是否在 O(n) 中具有相同的键，使用 O(1) 内存和允许递归。
你怎么做:两个同步中序遍历，这样就可以比较两个BST的ith<元素？
最佳答案
如何执行此操作取决于您的语言。
在像 Python 这样的语言中，您所做的就是使用 yield 编写 BST。这将创建一个保持少量状态的生成器。 (取决于数据结构和算法，在这种情况下它应该是O(1)或O(log(n))。众所周知，在现实世界中的 log(n) 是一个常数。尽管对于像 Google 这样的公司来说，它是一个稍大的常数...)
在没有 yield 的语言中，您需要安排创建一个对象，该对象具有关于搜索的状态，您可以调用该方法返回当前元素(或告诉您它已完成)，然后继续下一个。当您进入方法时保持状态并恢复它是公认的 PITA，但在幕后 Python 会为您做的事情。
如果您想感觉自己很聪明，可以尝试将必要的工作自动化。参见 http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html有关如何使用 C 预处理器在 C 中执行此操作的令人印象深刻的演示。 (这种技术实际上被用在了一个广泛使用的程序 PyTTY 中。)
关于algorithm - 检查两个二叉搜索树是否具有相同的键，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/38312483/