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

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); 
    }
}

我已经理解了为什么我的代码会抛出异常(因为left/right会指向null)。但是我想知道为什么第二种解决方案的原理几乎是一样的。提前感谢！

Answer 1

this在正在运行的类中永远不能为null。您将获得一个NPE，因为左==null或右==null的节点将无法调用size（）代码，因为指针没有引用任何内容。

也许您的代码应该更具防御性，并在尝试检索它们的大小之前检查子级是否为空：

public int size() {
    int total = 1;
    if (left != null)
        total += left.size();
    if (right != null)
        total += right.size();
    return total;
}

Answer 2

基本案例的组织方式错误；在当前实例上检查＜code＞null

public int size(){
    int sizeLeft = 0;
    if (this.left != null)
        sizeLeft = left.size();
    int sizeRight = 0;
    if (this.right != null)
        sizeRight = right.size();
    return 1 + sizeLeft + sizeRight;
}

Answer 3

在第一个示例中，您尝试在检查＜code＞null＜/code＞之前找到大小：

你先打电话

left.size()

然后在 size（） 方法中检查，以查看您刚刚调用该方法的对象是否为 null

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

因此，如果< code>left为< code>null，您将在进入< code>size()方法之前获得NPE。

这里要记住的主要事情是，this永远不能是null。如果是，您首先就不能在其上运行方法。所以您实际上并没有像您想象的那样在null案例上终止递归。

< br >

在第二个步骤中，首先检查< code>null:

如果refNode.left在此处为< code>null

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

size（）方法进行预检查

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

并安全地返回0。

< br >

您可以通过在每个分支上显式地将空检查放在第一个方法来使第一个方法工作：

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