Два перепутанных ключа
Индекс каталога хранится как двоичное дерево поиска: у каждого узла все ключи левого поддерева меньше его ключа, а все ключи правого — больше. После сбоя при записи у двух узлов могли поменяться местами ключи — сама форма дерева, все ссылки на детей, уцелела. А могло и обойтись. Проверьте индекс: если он в порядке, напишите OK, иначе найдите два перепутанных ключа.
Третий и четвёртый тесты — индекс по времени землетрясений 2025 года из каталога USGS, ключ — секунды от начала 2015 года. В третьем дерево строили, вставляя толчки от сильного к слабому, в четвёртом — по времени, и оно вытянулось в цепочку из двух с лишним тысяч узлов.
Вход
В первой строке n (2 ≤ n ≤ 10⁵) — число узлов. В следующих n строках описаны узлы 1, 2, …, n: ключ (целое от 1 до 10⁹, все ключи разные) и номера левого и правого ребёнка (0 — ребёнка нет). Корень — узел 1. Гарантируется, что входное дерево либо дерево поиска, либо получено из дерева поиска обменом ключей ровно двух узлов.
Выход
OK или два перепутанных ключа через пробел, меньший первым.
Примеры
Пример 1
7 50 2 3 30 4 5 70 6 7 20 0 0 40 0 0 60 0 0 80 0 0
OK
Пример 2
7 50 2 3 70 4 5 30 6 7 20 0 0 40 0 0 60 0 0 80 0 0
30 70
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 11 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Проверять каждый узел только против его детей мало: в первом примере, если поменять 50 и 40, корень 40 и его левый ребёнок 30 с правым ребёнком 50 по отдельности в порядке, а дерево — нет. Какой обход дерева поиска выдаёт ключи по возрастанию?
2Подсказка 2
Симметричный обход: левое поддерево, узел, правое поддерево. Как выглядит возрастающая последовательность, в которой поменяли местами два элемента? Сколько в ней мест, где следующий меньше предыдущего?
3Идея
Дерево — дерево поиска тогда и только тогда, когда его симметричный обход строго возрастает. Обмен двух ключей ломает возрастание в одном месте, если ключи были соседями по порядку, и в двух, если не были. Перепутаны левый элемент первого спуска и правый элемент последнего.
4Разбор
Пусть в отсортированной последовательности поменяли элементы на местах i < j. Большой элемент оказался на месте i и больше своего правого соседа — это первый спуск. Маленький оказался на месте j и меньше своего левого соседа — это последний спуск. Других спусков нет: остальные соседи стоят в исходном порядке. Если j = i + 1, оба спуска — одно и то же место.
Обход делаем циклом с явным стеком: спускаемся налево, кладя узлы на стек, снимаем узел, записываем ключ и переходим в правое поддерево. Рекурсия здесь опасна: в четвёртом тесте глубина дерева больше двух тысяч, в восьмом — 80 000, а Python по умолчанию останавливается на глубине 1000.
4+Решение
5Сложность
O(n) времени и O(n) памяти на последовательность и стек. Можно обойтись и памятью O(высота), если сравнивать каждый ключ сразу с предыдущим в обходе, не храня всю последовательность.
6Типичные ошибки
- Оба ключа из первого спуска. Верно, только если перепутанные ключи — соседи по порядку. Во втором примере обход даёт 20, 70, 40, 50, 60, 30, 80: спусков два, перепутаны 70 и 30, а не 70 и 40.
- Проверка родитель — ребёнок. Правило дерева поиска касается всех ключей поддерева, а не только детей.
- Рекурсивный обход. На цепочке из 80 000 узлов он упадёт в Python с ошибкой глубины рекурсии.
- Порядок вывода. Меньший ключ — первым.