c++ - 在 BST 中找到小于 K 的最大元素

Question

给定一个二叉搜索树和一个整数 K，我想找到小于 K 的最大元素。

在下面的树中，

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;
}

Answer 1

这是 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;
}