java - 测试两个二叉树是否相等的最有效方法

Question

您将如何在 Java 中实现二叉树节点类和二叉树类以支持最有效的(从运行时角度)相等检查方法(也必须实现):

    boolean equal(Node<T> root1, Node<T> root2) {}

或

    boolean equal(Tree t1, Tree t2) {}

首先，我按如下方式创建了 Node 类:

    public class Node<T> {
        private Node<T> left;
        private Node<T> right;
        private T data;

        // standard getters and setters
    }

然后是将 2 个根节点作为参数并运行标准递归比较的 equals 方法:

    public boolean equals(Node<T> root1, Node<T> root2) {
        boolean rootEqual = false;
        boolean lEqual = false;
        boolean rEqual = false;    

        if (root1 != null && root2 != null) {
            rootEqual = root1.getData().equals(root2.getData());

            if (root1.getLeft()!=null && root2.getLeft() != null) {
                // compare the left
                lEqual = equals(root1.getLeft(), root2.getLeft());
            }
            else if (root1.getLeft() == null && root2.getLeft() == null) {
                lEqual = true;
            }
            if (root1.getRight() != null && root2.getRight() != null) {
                // compare the right
                rEqual = equals(root1.getRight(), root2.getRight());
            }
            else if (root1.getRight() == null && root2.getRight() == null) {
                rEqual = true;
            }

            return (rootEqual && lEqual && rEqual);
        }
        return false;
    } 

我的第二次尝试是使用数组和索引来实现树的遍历。然后可以在两个数组上使用按位运算 (AND) 来完成比较——从 2 个数组中读取 block 并使用逻辑 AND 逐个屏蔽。我没能使我的代码正常工作，所以我没有在此处发布它(非常感谢您对第二个想法的实现以及您的改进)。

有什么想法可以最有效地对二叉树进行相等性测试吗？

编辑

这个问题假定结构平等。 (不是语义平等)

但是，测试语义相等性的代码，例如“如果它们的内容相同，即使它们的结构不同，我们是否应该认为这两棵树是相等的？”只是按顺序遍历树，它应该很简单。

Answer 1

一方面，您总是检查分支，即使您发现根不相等。如果您在发现不等式时立即返回 false，您的代码会更简单 (IMO) 并且更高效。

另一个简化事情的选择是允许您的 equals 方法接受 null 值并将两个 null 值比较为相等。这样您就可以避免在不同分支中进行所有这些无效检查。这不会提高效率，但会更简单:

public boolean equals(Node<T> root1, Node<T> root2) {
    // Shortcut for reference equality; also handles equals(null, null)
    if (root1 == root2) {
        return true;
    }
    if (root1 == null || root2 == null) {
        return false;
    }
    return root1.getData().equals(root2.getData()) &&
           equals(root1.getLeft(), root2.getLeft()) &&
           equals(root1.getRight(), root2.getRight());
} 

请注意，如果 root1.getData() 返回 null，目前这将失败。 (您添加节点的方式可能会也可能不会。)

编辑:正如评论中所讨论的，您可以使用哈希码来非常快速地“提前退出”——但这会增加复杂性。

或者您需要让您的树不可变(这是一个完整的其他讨论)或者您需要每个节点都知道它的父节点，以便当节点是更改(例如通过添加叶子或更改值)它需要更新其哈希码并要求其父级也更新。