通過遞歸確定整數二叉樹的大小

我有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）。但我想明白爲什麼第二種解決方案的準則是相同的。提前謝謝！

來源

2015-12-20 soupwaylee

第二個版本的作品，因爲你不嘗試調用一個方法上的空，你只需將null傳遞給函數。從第一個如果你知道refNode不是null – wastl

在你的第一個例子中，你試圖找出尺寸您檢查null前：

第一調用

left.size()

然後size()方法裏面你檢查是否對象你剛剛打電話的方法是null

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

所以如果left是null，那麼在進入size()方法之前，您將獲得NPE。

這裏要記住的主要事情是，this可以從來沒有是null。如果是這樣，首先你不可能在其上運行一種方法。所以你並沒有真正的終止你的遞歸，就像你以爲你是一個null案例。

在第二個你檢查null第一：

如果refNode。左邊是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 
}

來源

2015-12-20 18:37:16 azurefrog

this永遠不能在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; 
}

來源

2015-12-20 18:29:47 Rossiar

如果this不能爲null，則基本情況（if（ths == null）{...}'）應該被刪除，因爲它是沒有意義的。 – Turing85

感謝您的發現，我的副本不好 – Rossiar

基本情況是在錯誤的方式組織;在當前實例上檢查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; 
}

來源

2015-12-20 18:34:40 Codor

通過遞歸確定整數二叉樹的大小

回答

相關問題