root двоичного дерева поиска: у каждого узла все значения в левом поддереве меньше его значения, а в правом — больше. Все значения различны.
По ошибке значения ровно двух узлов поменяли местами, и свойство дерева поиска нарушилось. Исправьте дерево: верните эти два значения на свои места, не меняя форму дерева.
Верните корень исправленного дерева; чинить можно прямо на месте.
Решение с O(n) памяти напрашивается само. Сможете обойтись O(1) дополнительной памяти?root=tree_node([5, 8, 3, 1, 4]) → [5, 3, 8, 1, 4]
Симметричный обход даёт 1, 8, 4, 5, 3 — не по порядку стоят 8 и 3. Обмен их значений даёт дерево [5, 3, 8, 1, 4], где слева от каждого узла меньшие значения, справа — большие.
root=tree_node([3, 1, 2]) → [2, 1, 3]
Перепутаны соседние по порядку значения 2 и 3: после обмена корень равен 2, а его правый ребёнок — 3.
root=tree_node([10, 12, 15, 2, 7, 4, 20]) → [10, 4, 15, 2, 7, 12, 20]
root=tree_node([5, 8, 3, 1, 4])
[5, 3, 8, 1, 4]
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 35 тестов на сервере, включая скрытые.