Validate Binary Search Tree

Q: Почему проверки каждого узла относительно его дочерних узлов недостаточно для проверки корректности BST?

Правило распространяется на целые поддеревья. Узел, находящийся глубоко в правом поддереве корня, должен быть больше корня, даже если он является левым потомком гораздо большего узла. В [10, 5, 15, -1, -1, 6, 20] значение 6 вполне подходит на роль левого потомка 15 , но находится справа от 10 , поэтому это дерево не является деревом поиска. Нужны ограничения от всех предков, а не только от родителя.

Q: Какова временная сложность проверки бинарного дерева поиска?

Оба стандартных метода, проверка при симметричном обходе и проверка диапазонов, посещают каждый узел один раз, поэтому работают за время O(n) . Для стека проверке диапазонов требуется дополнительная память O(h) , где h — глубина. Сравнение каждого узла со всеми его поддеревьями тоже работает, но требует O(n × h) , что достигает O(n²) для дерева, имеющего форму цепочки.

Q: Можешь ли ты проверить BST с помощью симметричного обхода, не сохраняя каждое значение?

Да. При проверке симметричным обходом каждое значение сравнивается только с непосредственно предшествующим, поэтому храни предыдущее значение в переменной, а не в списке. Обойди дерево в симметричном порядке с помощью рекурсии или явного стека и верни false , как только значение окажется не больше предыдущего. Это сокращает дополнительную память до O(h) .

Q: Может ли бинарное дерево поиска содержать повторяющиеся значения?

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

СреднеДвоичное дерево поиска Обход деревьев

+10

Дано бинарное дерево, хранящееся в массиве tree в порядке уровней. Корень находится по индексу 0, дочерние узлы узла с индексом i находятся по индексам 2*i+1 (левый) и 2*i+2 (правый), -1 обозначает пустое место, а в конце массива могут быть дополнительные элементы -1.

Напишите функцию с именем isValidBST, которая возвращает true, если дерево является бинарным деревом поиска, и false в противном случае. В бинарном дереве поиска значение каждого узла строго больше любого значения в его левом поддереве и строго меньше любого значения в его правом поддереве. Два равных значения никогда не могут одновременно присутствовать в корректном дереве.

Функция

isValidBST(tree: integer-array) → boolean

treeinteger-array: бинарное дерево в порядке уровней, где -1 обозначает пустое место
Возвращаетboolean: true, если дерево является бинарным деревом поиска, иначе false

Ограничения

1 ≤ tree.length ≤ 32767
Каждый tree[i] равен -1 или содержит значение, для которого 0 ≤ tree[i] ≤ 10⁵.
tree[0] никогда не равно -1, поэтому в дереве есть хотя бы один узел.
После последнего узла в массиве могут оставаться дополнительные элементы -1.
Оба потомка пустого места тоже пусты, а глубина не превышает 14.
Значения могут повторяться.

Примеры

Ввод: tree = [8, 3, 12, 1, 6, 10, 15]
Вывод: true
Пояснение: Каждый узел находится с правильной стороны относительно всех узлов выше него. При чтении по порядку (левое поддерево, узел, правое поддерево) получаются значения 1, 3, 6, 8, 10, 12, 15, строго возрастающие, что и обеспечивает дерево поиска.

Ввод: tree = [10, 5, 15, -1, -1, 6, 20]
Вывод: false
Пояснение: Каждый узел больше своего левого потомка и меньше своего правого потомка, но дерево недопустимо. Значение 6 по индексу 5 находится в правом поддереве корня 10, поэтому оно должно быть больше 10, но это не так.

Ввод: tree = [12, 7, 12]
Вывод: false
Пояснение: Правый потомок корня содержит 12 — то же значение, что и корень. Правое поддерево должно быть строго больше, поэтому равное значение нарушает это правило.

+16 скрытых тестов при отправке

Дополнительный вопрос

Родитель узла с индексом i находится по индексу (i-1)/2, округлённому вниз. Сможешь обойти дерево по порядку, используя дополнительное пространство O(1) и переходя к родителям вместо хранения стека или рекурсивного вызова?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

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

Сравните каждый узел со всеми его поддеревьями

Идея

Сначала разберём, как перемещаться по массиву. У узла с индексом i левый потомок находится по индексу 2*i+1, а правый — по индексу 2*i+2. Потомок существует, только если его индекс находится внутри массива, а значение по этому индексу не равно -1. В массиве [10, 5, 15, -1, -1, 6, 20] корень 10 имеет потомков 5 и 15 с индексами 1 и 2, а у узла 15 есть потомки 6 и 20 с индексами 5 и 6.

Первая идея, которую пробует большинство, — сравнить каждый узел только с двумя его потомками. Вот дерево, на котором этот способ не работает: условия 5 < 10, 15 > 10, 6 < 15 и 20 > 15 выполняются, но узел 6 находится справа от 10. В определении говорится о каждом значении в поддереве, поэтому проверяйте именно это.

Для узла со значением v все значения слева меньше v тогда и только тогда, когда наибольшее значение слева меньше v. Точно так же все значения справа больше v, если наименьшее значение там больше v. Два небольших рекурсивных вспомогательных метода находят наибольшее и наименьшее значения. Для пустой стороны наибольшее значение равно -1, а наименьшее — 100001; эти значения выходят за допустимый диапазон, поэтому пустая сторона никогда не приводит к ошибке.

Этот способ верен, но он повторяет вычисления. Каждый узел просматривается по одному разу для каждого его предка, поэтому для дерева глубины h общее число посещений составляет примерно n × h. Здесь это подходит, поскольку глубина не превышает 14, но для дерева, представляющего собой единственный путь из n узлов, сложность возрастает до O(n²).

Алгоритм

Пройди по каждому индексу i, значение которого не равно -1.
Найди наибольшее значение в левом поддереве, которое начинается с 2*i+1, или -1, если это место пусто.
Найди наименьшее значение в правом поддереве, которое начинается с 2*i+2, или 100001, если это место пусто.
Если наибольшее значение больше или равно tree[i] или наименьшее значение меньше или равно tree[i], верни false.
После последнего узла верни true.

def isValidBST(tree):
    n = len(tree)

    def largest(i):
        # Largest value in the subtree at index i, or -1 when that spot is empty.
        if i >= n or tree[i] == -1:
            return -1
        return max(tree[i], largest(2 * i + 1), largest(2 * i + 2))

    def smallest(i):
        # Smallest value in the subtree at index i, or 100001 when that spot is empty.
        if i >= n or tree[i] == -1:
            return 100001
        return min(tree[i], smallest(2 * i + 1), smallest(2 * i + 2))

    for i in range(n):
        if tree[i] == -1:
            continue
        # Everything on the left must be smaller, everything on the right larger.
        if largest(2 * i + 1) >= tree[i] or smallest(2 * i + 2) <= tree[i]:
            return False
    return True

Значения при симметричном обходе должны строго возрастать

Идея

Обход в симметричном порядке посещает левое поддерево, затем узел, а потом правое поддерево. В двоичном дереве поиска значения в таком порядке отсортированы: всё, что находится слева, меньше и поэтому идёт первым, а всё, что находится справа, больше и поэтому идёт после. Первый пример даёт последовательность 1, 3, 6, 8, 10, 12, 15.

Верно и обратное, и именно это позволяет использовать такой обход для проверки. Возьмём любой узел v. В последовательности симметричного обхода всё его левое поддерево находится непосредственно перед ним, а всё правое — сразу после. Если последовательность строго возрастает, каждое значение перед v меньше, а каждое значение после него больше, поэтому правило выполняется для узла v и точно так же для любого другого узла.

Итак, обойдите дерево в симметричном порядке, соберите значения и сравните каждое с предыдущим. Второй пример даёт последовательность 5, 10, 6, 15, 20: переход от 10 к 6 показывает, что узел находится не на той стороне. Третий пример даёт последовательность 7, 12, 12, и повторяющееся значение 12 не проходит строгую проверку. Каждый узел посещается один раз, временная сложность — O(n), а для списка требуется O(n) памяти.

Алгоритм

Напишите walk(i): если ячейка пуста, остановитесь; иначе обойдите 2*i+1, добавьте tree[i], затем обойдите 2*i+2.
Вызовите walk(0), чтобы собрать значения по порядку.
Для каждой позиции k, начиная с 1, если values[k-1] ≥ values[k], верните false.
Верните true.

def isValidBST(tree):
    n = len(tree)
    values = []

    def walk(i):
        # Left subtree, then the node, then the right subtree.
        if i >= n or tree[i] == -1:
            return
        walk(2 * i + 1)
        values.append(tree[i])
        walk(2 * i + 2)

    walk(0)
    # A search tree read in order gives strictly increasing values.
    for k in range(1, len(values)):
        if values[k - 1] >= values[k]:
            return False
    return True

Передавайте допустимый диапазон вниз по дереву

Идея

Рассмотрите правило с точки зрения узла. Каждый предок устанавливает для него одно ограничение. Если узел находится в левом поддереве предка со значением a, его значение должно быть меньше a; если в правом поддереве — больше a. Все эти ограничения вместе образуют один открытый интервал (low, high), и узел находится на правильном месте, только если его значение строго попадает в этот интервал.

Этот интервал можно построить по мере спуска. Для корня ограничений нет. При переходе от узла со значением v к его левому потомку low остаётся прежним, а high уменьшается до v; при переходе к правому потомку high остаётся прежним, а low увеличивается до v. Новое ограничение всегда строже того, которое оно заменяет, потому что v само прошло проверку на соответствие прежнему интервалу.

Во втором примере для 15 задаётся интервал (10, no limit), который передаётся его левому потомку как (10, 15). Значение 6 меньше 10, поэтому проверка завершается неудачей сразу, и остальные узлы проверять не нужно. Значения находятся в диапазоне от 0 до 10^5, поэтому -1 и 100001 служат обозначениями «нет ограничения».

Храните ожидающие обработки узлы вместе с их интервалами в стеке. Каждый узел проверяется один раз: время O(n), а стек содержит ожидающие обработки узлы на одном пути: пространственная сложность O(h). При первом нарушении интервала поиск завершается.

Алгоритм

Поместите в стек (0, -1, 100001): индекс корня и открытый диапазон без реальных границ.
Извлеките (i, low, high). Если tree[i] не находится строго между low и high, верните false.
Если левый потомок 2*i+1 существует, поместите его в стек с диапазоном (low, tree[i]).
Если правый потомок 2*i+2 существует, поместите его в стек с диапазоном (tree[i], high).
Когда стек опустеет, верните true.

def isValidBST(tree):
    n = len(tree)
    # Each entry: a node index and the open range (low, high) its value must fall in.
    # -1 and 100001 lie outside every allowed value, so they mean "no limit".
    stack = [(0, -1, 100001)]
    while stack:
        i, low, high = stack.pop()
        value = tree[i]
        if not (low < value < high):
            return False
        left, right = 2 * i + 1, 2 * i + 2
        if left < n and tree[left] != -1:
            stack.append((left, low, value))  # the left side must stay below value
        if right < n and tree[right] != -1:
            stack.append((right, value, high))  # the right side must stay above value
    return True

Ловушки и крайние случаи

Большинство неправильных ответов проверяют слишком мало или проверяют нужное, но с неправильным сравнением.

Сравнение узла только с его потомками. В [10, 5, 15, -1, -1, 6, 20] каждая пара родитель–потомок выглядит правильной, но 6 всё равно нарушает ограничение, заданное корнем двумя уровнями выше.
Разрешение равных значений. Порядок строгий с обеих сторон, поэтому [12, 7, 12] недопустимо. Используй low < v < high и values[k-1] < values[k], никогда не используй ≤.
Передача вниз только значения родителя. Для левого потомка нужны оба ограничения: меньше значения родителя и больше любого нижнего ограничения, которое было у родителя. Передавай весь диапазон.
Выбор значения «без ограничения», которое может хранить узел. Значения начинаются с 0, поэтому нижнее ограничение 0 отклонило бы допустимый узел со значением 0, как в [0]. Начинай со значения меньше любого допустимого.
Чтение за пределами массива. Перед чтением потомка проверяй 2*i+1 < tree.length, а -1 считай отсутствующим потомком.
Путаница со смещением в Lua и R, где массивы начинаются с 1. Сохраняй индексы узлов нулевыми для вычисления 2*i+1 и читай tree[i + 1].

Частые вопросы4

Почему проверки каждого узла относительно его дочерних узлов недостаточно для проверки корректности BST?

Правило распространяется на целые поддеревья. Узел, находящийся глубоко в правом поддереве корня, должен быть больше корня, даже если он является левым потомком гораздо большего узла. В [10, 5, 15, -1, -1, 6, 20] значение 6 вполне подходит на роль левого потомка 15, но находится справа от 10, поэтому это дерево не является деревом поиска. Нужны ограничения от всех предков, а не только от родителя.

Какова временная сложность проверки бинарного дерева поиска?

Оба стандартных метода, проверка при симметричном обходе и проверка диапазонов, посещают каждый узел один раз, поэтому работают за время O(n). Для стека проверке диапазонов требуется дополнительная память O(h), где h — глубина. Сравнение каждого узла со всеми его поддеревьями тоже работает, но требует O(n × h), что достигает O(n²) для дерева, имеющего форму цепочки.

Можешь ли ты проверить BST с помощью симметричного обхода, не сохраняя каждое значение?

Да. При проверке симметричным обходом каждое значение сравнивается только с непосредственно предшествующим, поэтому храни предыдущее значение в переменной, а не в списке. Обойди дерево в симметричном порядке с помощью рекурсии или явного стека и верни false, как только значение окажется не больше предыдущего. Это сокращает дополнительную память до O(h).

Может ли бинарное дерево поиска содержать повторяющиеся значения?

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

Python

def isValidBST(tree):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

tree = [8, 3, 12, 1, 6, 10, 15]

Ожидается

true

Validate Binary Search Tree

Функция

Ограничения

Примеры

Подсказки

Решение

Сравните каждый узел со всеми его поддеревьями

Значения при симметричном обходе должны строго возрастать

Передавайте допустимый диапазон вниз по дереву

Ловушки и крайние случаи

Частые вопросы4

Похожие задачи