Java 简单的二叉树检查等于

Question

我不明白为什么这个 equals 函数不起作用：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
    
    public boolean equals(TreeNode other) {
        if (this == null && other == null) {
            return true;
        } else if (this == null || other == null) {
            return false;
        } else {
            return this.val == other.val
                    && this.left.equals(other.left)
                    && this.right.equals(other.right);
        }
    }
}

看来主要问题是我无法比较 null TreeNode，但在设置中我已经指出了如何处理 null？

TreeNode a = new TreeNode(5);
TreeNode b = new TreeNode(5);
System.out.println(a.equals(b)); // >>> NullPointerException

上面的比较从非空开始，但最终当分支到空左或空右时它会命中空。一种工作方式是将上面相同的方法提取到静态方法中：

public static boolean isEqual(TreeNode self, TreeNode other) {
    if (self == null && other == null) {
        return true;
    } else if (self == null || other == null) {
        return false;
    } else {
        return self.val == other.val
                && isEqual(self.left, other.left)
                && isEqual(self.right, other.right);
    }
}

这会很好用：

TreeNode a = new TreeNode(5);
TreeNode b = new TreeNode(5);
System.out.println(TreeNode.isEqual(a, b)); // >>> true

下面也可以，避免this.left/right变成null，看起来很傻，但确实是java

public boolean equals(TreeNode other) {

    if (this.left == null && other.left == null && this.right == null && other.right == null) {
        return this.val == other.val;
    } else if (this.left != null && other.left != null && this.right != null && other.right != null) {
        return this.val == other.val && this.left.equals(other.left) && this.right.equals(other.right);
    } else if (this.left != null && other.left != null && this.right == null && other.right == null) {
        return this.val == other.val && this.left.equals(other.left);
    } else if (this.left == null && other.left == null && this.right != null && other.right != null) {
        return this.val == other.val && this.right.equals(other.right);
    } else {
        return false;
    }
}

Answer 1

a 为空。因此，调用“equals”将立即引发 NullPointerException，而不会调用 equals 方法。

两个可能让您感到困惑的问题：

在第一个实现中，检查“this==null”是多余的（在此上下文中 this 不能为 null）。
“this.left”和“this.right”空检查也是多余的，因为它们是原语，永远不能为空。

我认为应该是这样的：

public boolean equals(TreeNode other) {
    if (other == null) {
        return false;
    }

    // Different Values
    if (this.val != other.val) {
        return false;
    }

    if (this.left == null && other.left != null) {
        return false;
    }
    if (this.left != null && !this.left.equals(other.left)) {
        return false;
    }
    
    if (this.right == null && other.right != null) {
        return false;
    }
    if (this.right != null && !this.right.equals(other.right)) {
        return false;
    }

    return true;
}

Java 简单的二叉树检查等于

Java Simple Binary Tree check equals

java

binary-tree

equals

data-structures