时间戳

首页 > 解决方案 > Java 简单二叉树检查等于

java - Java 简单二叉树检查等于

问题描述

我不知道为什么这个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;
    }
}

标签： javadata-structuresbinary-treeequals

解决方案

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

两个可能让你困惑的问题：

  1. 在第一个实现中，检查“this==null”是多余的（在这种情况下 this 不能为 null）。
  2. "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;
}

推荐阅读