Validate Binary Search Tree
Двоичное дерево хранится в массиве tree в порядке кучи: корень находится по индексу 0, потомки узла с индексом i — по индексам 2*i+1 (слева) и 2*i+2 (справа), -1 обозначает пустое место, а в конце массива могут быть дополнительные элементы -1.
Напишите isValidBST, которая возвращает true, если дерево является двоичным деревом поиска, и false в противном случае. В двоичном дереве поиска значение каждого узла строго больше любого значения в его левом поддереве и строго меньше любого значения в его правом поддереве.
Функция
- treeinteger-array
- двоичное дерево в порядке уровней, где -1 обозначает пустое место
- Возвращаетboolean
- true, если дерево является бинарным деревом поиска, false в противном случае
Ограничения
1 ≤ tree.length ≤ 32767- Каждый
tree[i]равен-1или значению, для которого0 ≤ tree[i] ≤ 105. 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.
- Ввод
- tree = [12, 7, 12]
- Вывод
- false
- Пояснение
- Правый потомок корня содержит
12, что равно значению корня. Правое поддерево должно быть строго больше, поэтому дерево не проходит проверку.
Дополнительный вопрос
Родитель узла находится по индексу (i-1)/2, округлённому вниз. Сможешь выполнить симметричный обход дерева, используя дополнительную память O(1) и перемещаясь по родителям вместо использования стека или рекурсии?
Подсказки
Открывайте по одной. Каждая подсказывает чуть больше.
В
[10, 5, 15, -1, -1, 6, 20]каждый узел больше своего левого потомка и меньше своего правого потомка. Почему это всё равно не дерево поиска?Каждый предок задаёт ограничение для узла: узел должен быть меньше него, если находится слева, и больше, если находится справа. Вместе эти ограничения образуют открытый диапазон. При переходе влево от значения
vверхняя граница снижается доv; при переходе вправо нижняя граница повышается доv.Храни стек
(index, low, high), начиная с корня и диапазона, который шире всех допустимых значений. Извлеки запись; если значение не находится строго внутри диапазона, заверши проверку с неудачей, а каждый существующий дочерний узел добавь в стек с его суженным диапазоном.
Решение
Это правило распространяется на целые поддеревья, поэтому сравнивать каждый узел с двумя его потомками недостаточно: узел, расположенный глубоко в дереве, может нарушить ограничение, заданное предком несколькими уровнями выше. Либо обойдите дерево в порядке возрастания и проверьте, что значения строго возрастают, либо передавайте каждому узлу диапазон, допустимый его предками.
Сравните каждый узел с его поддеревьями целиком
Идея
Каждое значение в левом поддереве узла меньше его значения v тогда и только тогда, когда наибольшее значение там меньше v, а каждое значение в правом поддереве больше v тогда и только тогда, когда наименьшее значение там больше v. Два рекурсивных вспомогательных метода находят эти значения. Для пустой стороны возвращается -1 или 100001 — значения за пределами диапазона, поэтому проверка никогда не завершается неудачей.
Для каждого предка каждый узел просматривается один раз: примерно n × h посещений для дерева глубины 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Значения при симметричном обходе должны строго возрастать
Идея
При симметричном обходе сначала посещается левое поддерево, затем узел, а потом правое поддерево, поэтому в бинарном дереве поиска значения считываются в отсортированном порядке.
Верно и обратное. Для любого узла v всё его левое поддерево идёт в последовательности непосредственно перед ним, а всё правое — непосредственно после него. Если последовательность строго возрастает, каждое значение перед v меньше него, а каждое значение после него — больше, поэтому правило выполняется для узла v и так же для каждого узла.
Во втором примере получается последовательность 5, 10, 6, 15, 20: спад от 10 к 6 выявляет неправильно расположенный узел. Каждый узел посещается один раз: время 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), и узел находится на правильном месте тогда и только тогда, когда его значение строго внутри этого интервала.
Формируйте интервал по мере спуска. Левый потомок сохраняет low и получает high = v; правый потомок сохраняет high и получает low = v. Во втором примере 15 передаёт интервал (10, 15) своему левому потомку, и проверка 6 сразу же завершается неудачей. Значения лежат между 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]— недопустимое дерево: сравнивайте с помощью<, а не≤. - Использование
0в качестве нижней границы «без ограничений». Это приводит к отклонению допустимого дерева[0]. - Чтение потомка без проверки
2*i+1 < tree.length. В[12, 7, 12]индекс3выходит за пределы массива. - В Lua и R массивы начинаются с 1. Используйте для индексов узлов нумерацию с 0, чтобы вычислять
2*i+1, и читайтеtree[i + 1].
Частые вопросы3
Какова временная сложность проверки бинарного дерева поиска?
Проверка симметричного обхода и проверка диапазонов посещают каждый узел один раз: время O(n), при этом для стека проверки диапазонов требуется дополнительное пространство O(h) на дереве глубины h. Сравнение каждого узла со всеми его поддеревьями требует O(n × h), что достигает O(n²) на дереве, имеющем форму пути.
Можно ли проверить, является ли BST корректным, с помощью симметричного обхода, не сохраняя каждое значение?
Да. Проверка сравнивает каждое значение только с предыдущим, поэтому храни предыдущее значение в переменной, а не в списке, и возвращай false, как только значение окажется не больше. Дополнительная память сокращается до O(h) для рекурсии или стека.
Может ли двоичное дерево поиска содержать повторяющиеся значения?
Не соответствует строгому определению, используемому здесь: равное значение не подходит ни для одной из сторон. В некоторых учебниках допускаются равные значения с одной стороны, например справа. Согласно этому правилу одно строгое сравнение становится ≤.
Похожие задачи
Задачи на те же идеи. Решите две или три, и приём запомнится.
def isValidBST(tree):
# Напишите код здесьТест #1
Тест #2
Тест #3
Аргумент
tree = [8, 3, 12, 1, 6, 10, 15]
Ожидаемый вывод
true