亞馬遜專訪：在BST的葉節點的總和

我已經爲此寫

sumBST(BST *root) 
    { 
     static sum =0; 
     if (root!= null) 
      { 
       if (root->left != null || root->right != null) 
       { 
        sum = sum + sumBST(root->left) + sumBST(root->right); 
        return sum; 
       } 
       else 
       { 
        root->data; 
       } 
      } 
     else 
      { 
       return 0; 
      } 
     return sum; 
    }

我已經畫遞歸樹檢查似乎很好，但我仍在某些時候，我做了一些困惑錯誤。請糾正我在這裏做錯事。

來源

2012-10-18 Nishant Kumar

好吧，它似乎並不像你實際上添加葉節點的總和。
在parcticular - 行：

root->data

實際上並不返回數據，只是讀取它。應該是這樣的，在僞代碼：

sumBST(node): 
    if (root == null): 
     return 0 
    else if (root->left == null && root->right == null) 
     //add the value of the node if it is a leaf, this step is missing 
     return root->data; 
    else: 
     return sumBST(root->left) + sumBST(root->right)

編輯：
在代碼的問題如下（澄清和進一步解釋在回答這一點）：

您應該將葉子的數據返回到某個地方 - 這不會發生在代碼中的任何地方 - 我懷疑您想返回root->data。

但是請注意，遞歸將轉到每一片葉子 - 它只是缺少從每個葉子返回值。

來源

2012-10-18 11:55:35 amit

但是，雖然我繪製我的代碼遞歸樹似乎確定你可以plz檢查，只是我想知道的方法，我跟着我的代碼工作與否... –

@Nishant請參閱編輯，我試圖澄清它，它全部連接到不返回'root-> data'。請注意，遞歸樹很好 - 它會訪問每個節點，但它只是缺少返回每個節點的值。 – amit

這個問題的目的主要集中在評估候選思考過程。

所有我在這裏看到的是一個錯字錯誤

root->data => return root->data

，並且永遠不會達到

return sum;

和一個超長指令

sum = sum + sumBST(root->left) + sumBST(root->right); => return sumBST(root->left) + sumBST(root->right);

面試官總是喜歡得到一個指令質疑他們給出的問題。這樣的問題，例如「BST是否給出了或者我可以設計一個針對給定葉片總和進行了優化的結構？」，「BST有多大？」......可以爲您的答案增加一個加號和最有可能的改變。

來源

2012-10-18 12:05:23

亞馬遜專訪：在BST的葉節點的總和

回答

相關問題