Вопрос

В этой статье мы рассмотрим Leetcode 230. K-й наименьший элемент в BST. Этот вопрос оценивается как Средний вопрос.

Вопрос:

По заданному rootбинарного дерева поискаи целому числу 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 в порядке возрастания. Это означает, что вы начинаете с наименьшего элемента и переходите к наибольшему элементу. Вот так: [1,2,3,4,5,6,7,8,9]. Думайте об этом как о отсортированном массиве.

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

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

Обозначение большого O:

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

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

Результаты литкода:

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

  • Время выполнения: 89 мс, быстрее, чем 44,57% при отправке JavaScript в Интернете для K-го наименьшего элемента в BST.
  • Использование памяти: 48,1 МБ, меньше чем 89,49% онлайн-заявок JavaScript для K-го наименьшего элемента в 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);
};