java - 在 Java 中测试两个 BST 是否相等

Question

我想测试两个给定的 BST(二叉搜索树)在 Java 中是否相等。 BST 节点没有指向父节点的指针。

最简单的解决方案是遍历两个 BST，创建两个遍历列表并测试列表是否相等。但是它需要 O(N) 内存。

我想尝试另一种方法:创建一个 Iterator，它遍历 BST，然后......剩下的就很明显了。

有意义吗？是否有任何“更好”(更简单和高效)的解决方案来测试两个 BSTs 是否相等？

Answer 1

1. 二叉搜索树是一棵树，对吧？

2. 如果两棵树具有相同的根和相同的 child ，则它们是相等的。

3. 每个 child 也是一棵树。

4. 参见第 2 点。

提示:recursion .内存消耗为O(logn)(自己证明)。