Найти наибольший элемент, меньший K в BST

Учитывая двоичное дерево поиска и целое число 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;
}

Ответ 1

Это O (log n), что является минимальным. Тем не менее, вы можете повысить эффективность (что, по-видимому, главное, о чем заботятся эти интервьюеры) и исключить возможность (tada!), Устраняя рекурсию хвоста, превращая это в цикл. Кроме того, ваш код не работает, если дерево содержит отрицательные числа... если вы имеете в виду неотрицательные целые числа, вы должны это сказать, но если интервьюер просто сказал "целые числа", вам нужен немного другой код и другой API. (Вы можете сохранить одну и ту же сигнатуру функции, но верните K вместо -1 при ошибке.)

BTW, так как это вопрос интервью, его реализация путем вызова функции библиотеки подскажет большинству интервьюеров, что вы являетесь смартфоном или упускаете точку или не знаете, как ее решить. Не вмешивайтесь в это дело, просто приступайте к работе над тем, что вы знаете, о чем хочет интервьюер.

Вот реализация:

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

Ответ 2

Думаю, идея здесь заключается в записи последнего node, после которого вы переходите к правильному поддереву. Поэтому код будет (обновлен)

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

Ответ 3

Я верю в использование стандартных библиотечных средств. Таким образом, мое решение использует 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;
}

Ответ 4

Я предлагаю вам ознакомиться с кодом в локальной реализации set:: upper_bound для руководства. Это не решение вашей конкретной проблемы, но очень близко.

В целом в реальной жизни большинство из этих проблем не нужно решать в вашем собственном коде. STL может выполнять множество общих задач для вас. Полезно знать, как их решить, следовательно, тест.

Ответ 5

Что сказал первый ответ, и вот логика, почему он не может стать лучше, чем 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

    }