在BST中找到小于K的最大元素 [英] To find largest element smaller than K in a BST

问题描述

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

Given a binary search tree and an integer K, i would like to find the largest element less than 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

我试过下面的逻辑。但是有没有更好的方法来做到这一点呢？

I tried the below logic. But is there any better way to do this ?

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

推荐答案

，这是最小的。然而，你可以提高效率（这似乎是这些访问者关心的主要事情），通过消除尾递归消除堆栈溢出（tada！）的可能性，把它变成一个循环。此外，如果树包含负数，你的代码不工作...如果你的意思是非负整数，你应该这样说，但如果面试官刚刚说整数，那么你需要稍微不同的代码和不同的API。 （你可以保持相同的函数签名，但失败时返回K而不是-1。）

That's O(log n), which is the minimum. However, you can improve the efficiency (which seems to be the main thing these interviewers care about) and eliminate the possibility of stack overflow (tada!) by eliminating tail recursion, turning this into a loop. Also, your code doesn't work if the tree contains negative numbers ... if you mean non-negative integers, you should say so, but if the interviewer just said "integers" then you need slightly different code and a different API. (You could keep the same function signature but return K instead of -1 upon failure.)

BTW，因为这是一个面试问题，通过调用库函数会告诉大多数采访者你是一个聪明的人或缺少点或不知道如何解决它。

BTW, since this is an interview question, implementing it by calling a library function would tell most interviewers that you are a smartass or are missing the point or don't know how to solve it. Don't mess around with that sort of thing, just get to working on what you know the interviewer wants.

这里是一个实现：

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

这篇关于在BST中找到小于K的最大元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！