要找到最大元素于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

回答

相关问题