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

Question

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

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

我想尝试另一种方式：创建一个Iterator，它遍历BSTs, 和 ... 其余的很明显。

是否有意义？是否有任何“更好”（更简单有效）的解决方案来测试两者BSTs是否相等？

Answer 1

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

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

3. 每个孩子也是一棵树。

4. 见第 2 点。

提示：递归。内存消耗是O(logn)（自己证明）。

Answer 2

最简单的方法可能是，创建两个树的哈希，然后检查它们是否相等。这仅适用于两棵树的内容也相同的情况。

如何创建校验和然后比较这些校验和。

http://www.mkyong.com/java/how-to-generate-a-file-checksum-value-in-java/

Answer 3

实现递归equals()方法。它不需要内存，并且很容易编码。

像这样的东西应该工作：

public class Node {

    Object value;
    private Node left;
    private Node right;

    public boolean equals(Object o) {
        if (o instanceof Node) {
            Node node = (Node)o;
            if (value.equals(node.value)) {
                return true;
            }
            return ((left == null && node.left == null) || left.equals( node.left)) && 
                    ((right == null && node.right == null) || right.equals( node.right));
        }
        return false;
    }
}

请注意，您应该重写hashCode()以反映此实现，因此请考虑将上述 impl 命名为，equalsDeep()并跳过该hashCode()impl。