Где применяется
1. Задача
В прошлом уроке ты строил дерево поиска вставками, поэтому правило порядка выполнялось само. Теперь дерево приходит извне: из загруженного файла, из индекса, который записала другая программа, из результата слияния двух деревьев. Прежде чем ему доверять, нужно проверить: это правда дерево поиска, где в каждом узле слева меньше, а справа больше?
Если нет, поиск по такому дереву будет молча возвращать неверные ответы. Поиск полагается на правило и отбрасывает целые поддеревья, не заглядывая в них.
Когда дереву можно доверять, появляется второй вопрос: какое значение третье по величине, если считать с наименьшего? Какое среднее по порядку (медиана)? Хочется получить k-е по порядку значение, не собирая все значения и не сортируя их.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитНа LeetCode
Задачи, где нужно проверить или использовать порядок двоичного дерева поиска целиком. Неси вниз границы low и high или иди обходом in-order, который читает значения по возрастанию.
isValidBST из урока, границы проверяются в каждом узле, а не только по родителю.
kthSmallest из урока, обход in-order останавливается после k узлов.
Обход in-order даёт значения по возрастанию, поэтому ответ равен наименьшему зазору между соседями в этом обходе.
В обходе in-order найди одно или два места, где значение падает, и поменяй местами два узла не на своих местах.