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

Question

我有 classes BinaryTreeNode(int value) 及其左右子节点和 BinaryTree(int rootVal)，其 BinaryTreeNode 根以 rootVal 作为其值。我开发了一个代码来计算树中的节点数（在 class 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永远不可能在运行class里面null。您将获得 NPE，因为具有 left == null 或 right == null 的节点将无法调用 size() 代码，因为指针不指向任何内容。

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

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

Answer 2

基本案例的组织方式有误；在当前实例上检查 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

在您的第一个示例中，您尝试在检查 null:

之前找到尺寸

先打电话给

left.size()

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

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

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

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

在第二个你首先检查 null:

如果 refNode.left 是 null 这里

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

size() 方法进行预检查

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

安全地 returns 0.

您可以通过明确地将 null 检查放在每个分支的第一位来使您的第一个方法起作用：

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

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

Determine size of Integer Binary Tree via recursion

java

recursion

binary-tree