无法将空值传递给 java 递归搜索

Question

我正在尝试编写一个简单的递归方法来查看二进制搜索树是否包含值。这就是我最初想到的：

static boolean doesContainData(Node root, int data){
    if (root.data == data){
        return true;
    }
    if (root == null){
        return false;
    }
    if (data > root.data){
        return doesContainData(root.right, data);
    }
    else if(data < root.data){
        return doesContainData(root.left, data);
    }
    return false;
}

然而，对于BST不包含带数据的节点的情况，它会向我抛出一个NullPointerException。经过一些测试，我意识到当我把功能改为这个时，它起了作用：

static boolean doesContainData(Node root, int data){
    if (root.data == data){
        return true;
    }
    if (root == null){
        return false;
    }
    if (data > root.data){
        if (root.right == null){
            return false;
        }
        return doesContainData(root.right, data);
    } 
    else if(data < root.data){
        if (root.left == null){
            return false;
        }
        return doesContainData(root.left, data);
    }
    return false;  
}

我不太清楚为什么后者有效，而前者无效。在后者中，我检查左/右节点是否为null，但我看不出这与原始方法有什么不同。在第一个方法中，我只是再次调用递归方法，它最终应该检查基本情况下的节点。

有什么想法吗？

Answer 1

一旦调用doeContainData（root.right，data）或doeContain data（root.left，data），就会调用您的方法dosContainData。

在这种情况下，如果root.left或root.right为null，当您调用以下方法时，

if (root.data == data){
    return true;
}

在root.data==数据被检查之前，root.data会抛出一个NullPointerException，因为它不存在。

但是，您稍后的方法将在调用doeContainData方法之前检查root.left或root.right是否为null。如果它为null，那么您的方法将返回false并终止。因此，最初的问题从未发生过。