java - 当预期和实际看起来相同时，为什么我会收到 AssertionError？

Question

我正在尝试从破解编码面试中回答以下问题。下面的代码是 GitHub 上一个项目的一部分，here .

Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (i.e., if you have a tree with depth D, you’ll have D linked lists).

作为一个优秀的小开发人员，我编写了一个单元测试来检查这一点。

@Test
public void testGetValuesAtEachLevel() {
    Integer[] treeValues = {
            1, 2, 3, 4, 5,
            6, 7, 8, 9, 10,
            11, 12, 13, 14, 15
    };

    tree = new GenericBinaryTree<>(treeValues);

    Integer[][] expectedArray = {
            { 1 },
            { 2, 3 },
            { 4, 5, 6, 7 },
            { 8, 9, 10, 11, 12, 13, 14, 15 }
    };

    List<List<Node<Integer>>> expectedList = new ArrayList<>(4);
    for (Integer[] level : expectedArray) {
        List<Node<Integer>> list = new LinkedList<>();
        for (Integer value : level) {
            list.add(new Node<>(value));
        }
        expectedList.add(list);
    }

    assertEquals(expectedList, tree.getValuesAtEachLevel());
}

这是代码。

List<List<Node<T>>> getValuesAtEachLevel() {
    List<List<Node<T>>> results = new ArrayList<>();

    List<Node<T>> firstLevel = new LinkedList<>();
    firstLevel.add(getRoot());
    results.add(firstLevel);

    loadAtLevel(results, 1);

    return results;
}

private void loadAtLevel(List<List<Node<T>>> list, int level) {
    List<Node<T>> levelList = new LinkedList<Node<T>>();

    for (Node<T> node : list.get(level - 1)) {
        if (node.left() != null) levelList.add(node.left());
        if (node.right() != null) levelList.add(node.right());
    }

    if (levelList.isEmpty()) return;

    level++;
    list.add(levelList);
    loadAtLevel(list, level);
}

想象一下当单元测试失败并出现以下错误时我的惊讶:

java.lang.AssertionError: expected: 
java.util.ArrayList<[[1], [2, 3], [4, 5, 6, 7], [8, 9, 10, 11, 12, 13, 14, 15]]> but was: 
java.util.ArrayList<[[1], [2, 3], [4, 5, 6, 7], [8, 9, 10, 11, 12, 13, 14, 15]]>

字符串表示是相同的，所以我无法弄清楚这里发生了什么。事实上，如果我将断言更改为此，测试通过:

    assertEquals(expectedList.toString(), tree.getValuesAtEachLevel().toString());

我感觉我将要学习一些关于接口(interface)和对象的非常有值(value)的东西。我在这里做错了什么？

Answer 1

正如@Jon Skeet 在评论中指出的那样，您需要覆盖 equals和 hashCode为您的Node类，对其实例执行比较 (equals)。

样本(使用 IntelliJ 默认自动生成)可以是 -

@Override
public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;

    Node<?> node = (Node<?>) o;

    if (left != null ? !left.equals(node.left) : node.left != null) return false;
    if (right != null ? !right.equals(node.right) : node.right != null) return false;
    if (parent != null ? !parent.equals(node.parent) : node.parent != null) return false;
    return value != null ? value.equals(node.value) : node.value == null;

}

@Override
public int hashCode() {
    int result = left != null ? left.hashCode() : 0;
    result = 31 * result + (right != null ? right.hashCode() : 0);
    result = 31 * result + (parent != null ? parent.hashCode() : 0);
    result = 31 * result + (value != null ? value.hashCode() : 0);
    return result;
}

另一方面为什么

assertEquals(expectedList.toString(),tree.getValuesAtEachLevel().toString());

作品。

这是因为您在这里最后要断言的是比较两个 String具有 @Override 的实例n equals定义 here