Решение разработано в:

Вопрос

В этой статье мы рассмотрим вопрос Leetcode ‘230. Kth Smallest Element in a BST». Этот вопрос оценивается как средний.

Вопрос:

Учитывая корень дерева двоичного поиска и целое число k, верните k наименьшее значение (1-индексированное) из всех значений узлов дерева.

Пример:

     3
    / 
   1   4
    
     2

Input: root = [3,1,4,null,2], k = 1
Output: 1

Объяснение вопроса

Этот вопрос оценивается как средний. Что, на мой взгляд, соответствует действительности.

Вопрос заключается в том, чтобы найти k наименьший элемент. Итак, если k равен 1, то нам нужно найти наименьший элемент в BST. Если k равен 2, то нам нужно найти второй наименьший элемент в BST.

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

Проблема в том, что k потенциально может быть последним узлом в BST. Поэтому мы знаем, что будем использовать какую-то форму обхода для обхода всего дерева. Поскольку нам, возможно, придется это сделать.

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

Теперь вы можете обойти BST и сохранить его в стеке. Затем просто вернуть k элемент этого стека. Но это уменьшит среднюю временную и пространственную сложность нашего алгоритма. Мы поступим умнее и просто перейдем к узлу k в BST и вернем его. Это означает, что наша пространственная сложность будет лучше, как и наша временная сложность.

Рекомендуемые знания

1. Двоичное дерево
2. Поиск по глубине
3. Порядковый обход
4. Двоичное дерево поиска
5. Рекурсия

Что мы знаем?

1. Нам дано дерево двоичного поиска и целое число k.
2. Нам нужно найти k наименьший элемент в BST.
3. Мы используем дерево двоичного поиска. Поэтому для обхода BST в порядке возрастания мы можем использовать обход с поиском по глубине.
4. Учитывая обход в порядке возрастания, мы можем обойти k узлов в BST. Это то же самое, что и k наименьший элемент в BST.

Как мы это сделаем:

Решение этой проблемы заключается в использовании обхода с поиском по глубине в порядке возрастания для обхода BST в порядке возрастания. Это означает, что после обхода k узлов в BST мы можем вернуть значение узла.

Это бессмысленно?!?!!

Я знаю, я знаю, я знаю. Для меня это тоже не имело смысла. Только после того, как я сделал Восстановление дерева двоичного поиска, это в конце концов обрело смысл.

Подумайте вот о чем: когда вы выполняете обход BST в порядке возрастания, вы собираетесь обходить BST в порядке возрастания. Это означает, что вы начинаете с наименьшего элемента и переходите к наибольшему. Например, так:

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

1. Объявим глобальный флаг для отслеживания результата возврата. Это будет значение узла k. Это просто облегчает нам жизнь
2. Выполните обход с поиском по глубине в порядке возрастания, чтобы обойти BST в порядке возрастания.
3. Каждый раз, когда мы перемещаем узел, мы будем уменьшать значение k. Итак, K-=1, пока мы не достигнем узла k (k === 1). Это означает, что мы сейчас находимся на узле k. Здесь мы устанавливаем глобальный флаг на значение узла k.
4. Верните это значение в любое место.

Нотация Big O:

• Временная сложность: O(n)| Где n — количество узлов в нашем дереве двоичного поиска | Так как в худшем случае мы собираемся обойти все BST. Поскольку K — это количество узлов в BST.
• Пространственная сложность: O(h)| Где h — высота дерева двоичного поиска | Потому что мы будем хранить высоту дерева в стеке вызовов из-за обхода в порядке возрастания.

Можно ли это улучшить? Да! Morris Traversal мог бы решить эту задачу с пространственной сложностью O(1). Но Morris Traversal сложен и труден для чтения. Для простоты я не использую его здесь.

Результаты Leetcode:

См. ссылку на представление:

• Время выполнения: 89 мс, быстрее, чем 44.57% онлайн-заявок JavaScript для K-го наименьшего элемента в BST.
• Использование памяти: 48,1 МБ, меньше, чем в 89,49% случаев использования JavaScript для Kth Smallest Element in a BST.

Решение

var kthSmallest = function (root, k) {



    // This is what is ultimately returned in the end
    // This is also used as a flag to let our in-order traversal know when to stop / stop traversing
    let return_result = null;

    // We're going to traverse the BST in-order
    // Why? Well, we want to find the kth smallest element, correct?
    // One of the cool tricks about a BST is that it's a sorted tree
    // So if you traverse the tree 'in-order' you'll always start at the smallest element
    // then to the second smallest, then third smallest, etc.
    // Try it out! Slap a console.log in the middle of the in-order traversal to see what it does
    const in_order_traversal = (node) => {

        // So, we have either reached the end of the tree or we have found the kth smallest element
        if (!node || return_result) {
            return return_result;
        }

        // Traverse the left subtree
        in_order_traversal(node.left);

        // So, k === 1, meaning, we're now on 
        // the desired node and as to not repeat
        // the same node, we'll check that the return_result
        // hasn't already been set
        if (k === 1 && return_result === null) {

            // Set the return result to the current nodes value
            // as this node is the kth smallest element
            return_result = node.val;

            // Also return it. As to stop the in-order traversal
            return return_result;
        } else {

            // So, we're not on the desired node
            // Decrement by 1. 
            k -= 1;
        }

        // Traverse the right subtree
        in_order_traversal(node.right);

        // Return the result
        return return_result;
    };

    return in_order_traversal(root);
};