要找到最大元素於K在BST

鑑於二叉搜索樹和一個整數K，小，我想找到最大的元素比K.要找到最大元素於K在BST

少

在下面的樹，

for K = 13, result = 12 
for K = 10, result = 8 
for K = 1 (or) 2, result = -1 

     10 

    5  12 

2 8 11 14

我嘗試了下面的邏輯。但是有沒有更好的方法來做到這一點？

int findNum(node* node, int K) 
{ 
     if(node == NULL) 
     { 
       return -1; 
     } 
     else if(K <= node->data) 
     { 
       return findNum(node->left,K); 
     } 
     else if(K > node->data) 
     { 
       int t = findNum(node->right,K); 
       return t > node->data ? t : node->data; 
     } 

     return -1; 
}

來源

2011-06-13 joshu

我看不錯。 – 2011-06-13 18:26:48

如果您發現K-1，您應該終止。我不能從你的代碼中知道你是否正在做這件事（儘管可能很明顯，我不知道C++）。 – PengOne 2011-06-13 18:27:56

請定義「更好」。更高效？更準確？ – 2011-06-13 18:30:07

這是O（log n），這是最小值。但是，您可以通過消除尾遞歸來提高效率（這似乎是這些採訪者關心的主要問題），並消除堆棧溢出（tada！）的可能性，從而將其變爲循環。此外，如果樹包含負數，則代碼不起作用...如果您的意思是非負數整數，您應該這樣說，但如果面試官只是說「整數」，那麼您需要稍微不同的代碼和不同的代碼API。（你可以保留相同的功能簽名，但在失敗時返回K而不是-1。）

順便說一下，因爲這是一個面試問題，通過調用庫函數實現它會告訴大多數面試官你是聰明人還是錯過了點或不知道如何解決它。不要混淆這類事情，只要開始研究你知道面試官想要的東西。

這是一個實現：

// Return the greatest int < K in tree, or K if none. 
int findNum (Node* tree, int K) 
{ 
    int val = K; 

    while(tree) 
     if(tree->data >= K) 
      tree = tree->left; 
     else{ 
      val = tree->data; 
      tree = tree->right; 
     } 

    return val; 
}

來源

2011-06-13 19:25:34

我建議您通過本地實施set::upper_bound中的代碼來獲取指導。這不是解決您的具體問題，但非常接近。

通常在現實生活中，大多數這些問題不需要在您自己的代碼中解決。 STL可以爲您執行許多常見任務。當然知道如何解決它們是有用的，因此測試。

來源

2011-06-13 18:29:02

我相信使用標準的圖書館設施。因此，我的解決方案使用std::set。 :-)

int largest_num_smaller_than(std::set<int> const& set, int num) 
{ 
    std::set<int>::const_iterator lb(set.lower_bound(num)); 
    return lb == set.begin() ? -1 : *--lb; 
}

來源

2011-06-13 18:33:25

我覺得這裏的想法是記錄之後您移動到右子樹的最後一個節點。因此，該代碼將（已更新）

int findNum (Node *node, int K) 
{ 
    Node* last_right_move = NULL; 

    while (node) 
    { 
     if (K<=node->data) 
      node = node->left; 
     else 
     { 
      last_right_move = node; 
      node = node->right; 
     } 
    } 

    if (last_right_move) 
     return last_right_move->data; 
    else 
     return NOT_FOUND; // defined previously. (-1 may conflict with negative number) 
}

來源

2011-06-14 02:06:21 badawi

第一個答案說的話，這裏的背後是爲什麼它不能比O（log n）的更好的邏輯。您正在尋找的最小號碼小於K.這與BST-search/get相當接近。

雖然原來的算法看起來相當不錯，我認爲這將是更快：

int findNum (node root, int K) { 
     if(root == null) return -1; 

     if(K > root.val) { 
      if(root.right != null) return findNum(root.right, K);    
      else return root.val; 
     } 

     return findNum(root.left, K); //look in left subtree 

    }

來源

2011-07-27 10:11:27

要找到最大元素於K在BST

回答

相關問題