加總二進制樹級別

-1

我試圖遍歷一個二進制樹的級別，然後求和保存在levelSum中保存的每個級別的每個節點中的整數。然後，我想將levelSum乘以我所在的級別的數字，並將其添加到totalSum中。當我運行它時，我在第15行得到一個NullPointException，但我一直無法弄清楚爲什麼。加總二進制樹級別

public int depthSum() { 
    Queue<IntTreeNode> q = new LinkedList<IntTreeNode>(); 
    int totalSum = 0; 
    int levelSum = 0; 
    int multiplier = 1; 
    int nodesPerLevel = 0; 
    if(overallRoot != null) { 
        q.offer(overallRoot); 
     nodesPerLevel += 1; 
        while(!q.isEmpty()) { 
      int countDown = nodesPerLevel; 
      while(countDown > 0) { 
       countDown--; 
       IntTreeNode n = q.remove(); 
       levelSum += n.data; //this is line 15 
       if(n.left != null) { 
        q.offer(n.left); 
        nodesPerLevel++; 
       } 
       if(n.right != null) { 
        q.offer(n.right); 
        nodesPerLevel++; 
       } 
      } 
      totalSum += (multiplier * levelSum); 
      levelSum = 0; 
      multiplier++; 
     } 
    } 
    return totalSum 
}

這是堆棧跟蹤：

NullPointerException on line 15: 
java.lang.NullPointerException 
at IntTree.depthSum (Line 15)

來源

2014-06-18 Joshua Oliphant

一如往常：堆棧跟蹤請。哪一行是第15行？ – Seelenvirtuose

這行是15：'tempSum + = n.data;'？ – AlexR

是的，這是第15行。只是添加了一條評論來顯示它。 –

如果我不得不猜測，可能countdown不具有正確的值;然而，由於很多變量在代碼中是未定義的，因此很難準確地確定故障發生的位置。如果countdown有問題，內部循環將最終清空隊列。發生這種情況時，您將獲得n = null，並試圖撥打n.data,n.left或n.right將給出NullPointerException。

下面是什麼，我認爲你正在嘗試做的（Ideone example here）類似的版本：

public int depthSum(IntTreeNode root) { 
    if(root == null) throw new NullPointerException(); 

    Queue<IntTreeNode> q = new LinkedList<IntTreeNode>(); 
    q.add(root); 
    int siblings = 1; 
    int totalSum = 0, levelSum = 0, level = 0; 

    while(!q.isEmpty()) { 
     IntTreeNode n = q.remove();   // Only remove one node per loop 
     levelSum += n.data; 

     if(n.left != null)      // Add left child 
      q.add(n.left); 

     if(n.right != null)     // Add right child 
      q.add(n.right); 

     if(--siblings == 0){     // All siblings have been probed 
      siblings = q.size();    // All remaining Nodes are siblings 
      totalSum += levelSum * level;  // increment totalSum 
      level++;       // increment level 
      levelSum = 0;      // reinitialize levelSum 
     } 
    } 
    return totalSum; 
}

來源

2014-06-18 06:59:48 bcorso

-1

爲NullPointException主要的一點應該是不nodesPerLevel重置爲0; countDown應該大於隊列大小並導致q.remove拋出NullPointException。

nodesPerLevel應該在countDown = nodesPerLevel之後重置爲0。

此代碼段看起來無法編譯，例如tempSum看起來是levelSum。所以最終結果需要驗證。

來源

2014-06-18 06:56:27

'nodesPerLevel'永遠不會在此代碼中提供'NPE'，因爲它的類型是原始類型。 – Andremoniy

@Andremoniy，謝謝你的評論，我很高興我的回答得到了迴應。你是對的，** nodePerLevel **不給** NPE **。但由於** nodesPerLevel **未重置爲** 0 **，所以它將大於** q **的大小並導致** q.remove ** throw ** NPE **。 –

加總二進制樹級別

回答

相關問題