Validate Binary Search Tree

Средняя№98симметричный

Дан корень двоичного дерева. Нужно сказать, двоичное ли это дерево поиска: в каждом узле все значения левого поддерева меньше узла, а все значения правого — больше. Наше дерево: 10 с потомками 5 и 15; у 15 потомки 6 и 20 — ответ false: 6 лежит в правом поддереве 10, но меньше 10.

98 Validate Binary Search TreeРазбор · 1×

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

nonenonenonenonenonenone10515620по порядку—стек вызововвершина справа—
не посещёнждёт в стеке вызововтекущий вызовprev, сравниваем с узломуже по порядку, ↑ что вернулnone: пустой потомок

prev = none: пока ни одного значения

01/29
сначала · назад · пуск · шаг
Скорость
1function isValidBST(root):
2 prev = none // shared by every call of inorder
3 return inorder(root)
4
5function inorder(node):
6 if node is none:
7 return true
8 if not inorder(node.left):
9 return false
10 if prev is not none and node.val <= prev:
11 return false
12 prev = node.val
13 return inorder(node.right)
состояние
node
–
prev
–
нажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Дерево — BST ровно тогда, когда при симметричном обходе значения строго растут, поэтому достаточно сравнить каждое значение с prev — тем, что прямо перед ним.
  2. Сравнивать узел только с потомками мало: 6 < 15 — нормально для левого потомка, но 6 лежит справа от 10. По порядку 6 идёт сразу за 10, тут проверка и срабатывает.
  3. Первый false сразу поднимается через все вызовы, поэтому остаток дерева не посещаем.

Сложность

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

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.