如何找到給定深度的節點值的和如果樹不完整？

我已經問過非常類似的問題，應該提到更詳細的。上次在PHP中是「如何在二叉樹中找到給定深度的節點值的和」。如何找到給定深度的節點值的和如果樹不完整？

sum(Node, Level) = 
    if (Level == 0) return Node.value; 
    else return f(Node.left, Level-1) + 
       f(Node.right, Level-1).

所以現在我試着用Java寫這個。 Java拋出nullPointerException。原因是因爲下面的代碼在樹不完整的情況下無法處理。

public int getNodeValueByDepth(Node n, int level) { 

      if(level == 0) { 
       return n.data; 
      } 
      else { 
       return getNodeValueByDepth(n.left, level-1) + 
         getNodeValueByDepth(n.right, level-1); 
      } 
    }

我測試樹結構是：

/* 
     * construct tree 
     *         sum of node's value 
     *    5   depth 0 ==> 5 
     *   /\    
     *   3 10  depth 1 ==> 13 
     *  /\ /\ 
     *   2 4 6 11 depth 2 ==> 23 
     *    /\ 
     *    7 9  depth 3 ==> 16 
     *    
     *       depth 4 ==> null 
     *   
     */

因此，當我打電話getNodeValueByDepth（根，3），它是7 + 9，它引發和空指針異常錯誤。我試圖添加邏輯來處理左右節點爲空的情況，但仍然無法弄清楚如何解決此問題我無法入睡。

任何人都可以給我一個提示嗎？我試過，但它不只是返回0

public int getNodeValueByDepth(Node n, int level) { 

     int sum = 0; 

     if(level == 0) { 
      return sum + n.data; 
     } 
     else if(n.left != null) { 
      return sum += getNodeValueByDepth(n.left, level-1); 
     } 
     else if(n.right != null) { 
      return sum += getNodeValueByDepth(n.right, level-1); 
     } 
     else { 
      return sum + 0; 
     } 

    }

來源

2010-07-13 masato-san

你的控制語句在任何情況下使用else，所以只有一個曾經被評估。因此，如果它評估左側，當它返回時，它不會做右側。

public int getNodeValueByDepth(Node n, int level) { 
    int sum = 0; 

    /** If we have reached our desired level */ 
    if (level == 0) { 
     if (n != null) { 
      /** Assuming data is an int and not nullable */ 
      return n.data; 
     } else { 
      /** Change this to 0 if you don't want an error condition */ 
      return -1; 
    } 

    /** We are not the desired level, so get the sum of .left and .right, knowing either may not exist */ 
    if (n.left != null) { 
     sum += getNodeValueByDepth(n.left, level-1); 
    } 

    if (n.right != null) { 
     sum += getNodeValueByDepth(n.right, level-1); 
    } 

    /** Now have evaluated every possible child and stored the sum, even if it is 0 */ 
    return sum; 
}

注意：檢查語法錯誤，我在沒有Java的機器上寫這個。

來源

2010-07-13 20:07:18 Andy

當我打電話給getNodeValueByDepth（root，3）時返回了9，但是我認爲我們已經接近了..現在檢查更多細節.. – 2010-07-13 20:15:55

ahh！對不起，我認爲我的示例樹結構有bug，7應該是9的孩子。所以你的代碼是正確的。 – 2010-07-13 20:19:56

在最後一個例子中，取出最後一個「Else」，讓它返回總和，而不管前面的條件是否成功，它應該工作。

來源

2010-07-13 20:08:12

如何找到給定深度的節點值的和如果樹不完整？

回答

相關問題