В этой статье мы рассмотрим Leetcode ’98. Вопрос Проверить бинарное дерево поиска. Этот вопрос оценивается как Средний вопрос.

Вопрос:

Учитывая root двоичного дерева, определите, является ли оно допустимым двоичным деревом поиска (BST).

Действительный BST определяется следующим образом:

  • Левое поддерево узла содержит только узлы с ключами меньше ключа node.
  • Правое поддерево узла содержит только узлы с ключами больше ключа node.
  • И левое, и правое поддеревья также должны быть бинарными деревьями поиска.

Пример:

Input: root = [2,1,3]
Output: true

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

Рейтинг этого вопроса средний. Что я считаю точным. Этот вопрос идеально подходит для изучения Двоичных деревьев поиска и Обхода дерева по порядку.

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

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

Решение, которое я собираюсь объяснить, будет иметь применимые знания ко многим другим проблемам.

  1. 99. Восстановить двоичное дерево поиска

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

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

Что мы знаем?

  1. Нам предоставлено Двоичное дерево поиска. Это может быть действительным или нет.
  2. Нам нужно подтвердить это.
  3. Их всегда будет как минимум 2 узла.

Как мы собираемся это сделать:

По сути, мы собираемся пройтись по бинарному дереву в по порядку. Это означает, что посещаемый нами узел СЛЕДУЮЩИЙ всегда должен быть больше, чем предыдущий узел. Если это не так, то мы сразу знаем, что дерево недействительно.

  1. Установите flag в true, этот флаг будет использоваться, чтобы сообщить нам, действительно ли дерево или нет. По умолчанию он всегда действителен. Пока мы не найдем узел, который меньше предыдущего узла.
  2. Мы объявим указатель на предыдущий узел, так как мы собираемся отслеживать наш предыдущий узел при обходе дерева по порядку.
  3. Мы будем выполнять обход дерева по порядку, спрашивая в каждой точке обхода: «Текущий узел меньше предыдущего?» Если да, то мы знаем, что дерево недействительно. Поэтому мы устанавливаем flag на false.
  4. Если плохие узлы не найдены, мы знаем, что дерево правильное, и флаг остается нетронутым.

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

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

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

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

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

  • Время выполнения: 67 мс, быстрее, чем 94,56 % онлайн-отправок JavaScript для проверки дерева двоичного поиска.
  • Использование памяти: 46,8 МБ, менее 22,46% онлайн-заявок JavaScript для проверки дерева двоичного поиска.

Решение

var isValidBST = function (root) {
    // This is the flag that will be returned
    // In the event we find a node that violates the BST property, we inverted the flag.
    let is_bst_valid = true;
    // We will also be tracking the previous node.
    // This will be used to check if the current node is greater than the previous node.
    // As a valid BST, the previous node must be less than the current node.
    let prev_node = new TreeNode(-Infinity, null, null);
    // We will traverse the tree in-order.
    // As a BST traversed in-order would result in something akin to a sorted array.
    // [1,2,3,4,5,6,7,8,9]
    // In the event we see something like this:
    // [1,2,3,4,*99,6,7,8,9,10]
    // We know it's not a valid BST.
    const in_order_traverse = (node) => {
        // Empty tree. Base case.
        if (!node || !is_bst_valid) {
            return;
        }
        // Get my left nodes.
        in_order_traverse(node.left);
        // The in order section
        // Check if the current node is greater than the previous node.
        // If not, it's a invalid tree
        if (node.val <= prev_node.val) {
            is_bst_valid = false;
        }
        // Update the previous node.
        prev_node = node;
        in_order_traverse(node.right);
    };
    in_order_traverse(root);
    // Return the flag
    return is_bst_valid;
};