通过递归确定整数二叉树的大小

Question

我有BinaryTreeNode(int值)及其左右子类和BinaryTree(int rootVal),BinaryTreeNode根,其中rootVal为其值.我开发了一个代码来计算树中的节点数(在BinaryTreeNode类中),但是由于NullPointerException它不起作用:

public int size(){
    if(this == null) {    // base case
        return 0;
    } else {
        return 1 + left.size() + right.size();
    }
}

然而,我发现的另一种解决方案,采用类似的策略,有效:

public int size(BinaryTreeNode refNode){
    if(refNode == null) {    // base case
        return 0;       
    } else {
        return 1 + size(refNode.left) + size(refNode.right); 
    }
}

我已经理解为什么我的代码抛出异常(因为左/右指向null).但我想理解为什么第二种解决方案与准原理相同.先感谢您!

Answer 1

在第一个示例中，您尝试在检查之前找到尺寸null：

首先你打电话

left.size()

然后在size()方法内部检查您刚刚调用该方法的对象是否是null

if(this == null) {    // base case
    return 0;
...

所以如果left是null，你在进入size()方法之前就得到了NPE。

这里要记住的主要事情是，这永远this不可能。如果是，那么您一开始就无法在其上运行方法。所以你实际上并没有像你想象的那样终止你的递归。nullnull

在第二个中，您首先检查null：

如果 refNode.left 在null这里

    return 1 + size(refNode.left) + size(refNode.right); 

该size()方法进行预检查

if(refNode == null) {    // base case
    return 0;
...

并安全返回0。

您可以通过在每个分支上显式地首先放置空检查来使您的第一个方法起作用：

public int size(){
    return 1 
        + left == null ? 0 : left.size()    // check for null first
        + right == null ? 0 : right.size(); // check for null first
}