一千萬個為什麽

搜索

二叉樹hasPathSum()實現

你好 我正在嘗試實現 hasPathSum() 對於給定數字的意思是在根到葉節點之間存在任何路徑。

我從斯坦福網站上獲得了這段代碼。我認為這是錯誤的

/** 
 Given a tree and a sum, returns true if there is a path from the root 
 down to a leaf, such that adding up all the values along the path 
 equals the given sum. 
 Strategy: subtract the node value from the sum when recurring down, 
 and check to see if the sum is 0 when you run out of tree. 
*/ 

boolean hasPathSum(Node node, int sum) { 
 //return true if we run out of tree and sum==0 
  if (node == null){ 
    return(sum == 0); 
  } 
  else { 
 //otherwise check both subtrees 
    int subSum = sum - node.data; 
    return(hasPathSum(node.left, subSum) || hasPathSum(node.right, subSum)); 
  } 

這是正確的實施嗎?

我想這如果應該是

  • if(node.left==null && node.right==null)

如果我錯了請清除我的困惑

考慮這種情況:

          5
        /\
        2   1
      /   
      3

-謝謝

最佳答案

由於伯特沒有解決他的答案,我會發布正確的答案。

是的,盡管大多數人都在說,原始代碼已被破壞,你說得對。在你的例子中

      5
    /\
    2   1
  /   
  3

調用

hasPathSum(root, 7);

將返回 true ,盡管沒有添加到7的root-to-leaf路徑。這是因為當到達node 2 時,它會遞歸檢查正確的子節點(使用sum 0),然後返回true,因為右邊的孩子是 null

該修復的靈感來自Bert的答案:

// `if` statement should check children and `return` statement deduct node.data from sum
boolean hasPathSum(Node node, int sum) { 
  int subSum = sum - node.data; 
  if(node.left==null && node.right==null) { 
    return(subSum == 0); 
  } 
  else { 
   //otherwise check both subtrees 
    if ( node.left != null && hasPathSum(node.left, subSum) ) {
        return true;
    if ( node.right != null && hasPathSum(node.right, subSum) ) {
        return true;
    }
    return false;
  } 
}

如果你想要(很多ands和ors),你可以將else塊轉換成一個長語句,但我發現它更幹凈。

轉載註明原文: 二叉樹hasPathSum()實現