root двоичного дерева из n узлов со значениями от 1 до n, все значения разные. Ещё дан маршрут route — перестановка чисел от 1 до n, в которой хочется увидеть узлы при прямом обходе (preorder: узел, потом левое поддерево, потом правое).
За одну операцию можно выбрать узел и поменять местами его левое и правое поддеревья.
Сделайте наименьшее число таких операций, чтобы прямой обход совпал с route, и верните значения узлов, у которых меняли детей, в любом порядке. Если совпадения добиться нельзя, верните [-1].root=tree_node([1, 2, 3, 4]), route=[1, 3, 2, 4] → [1]
Без перестановок прямой обход 1, 2, 4, 3. Меняем детей узла 1 местами — получаем 1, 3, 2, 4.
root=tree_node([1, 2, None, 3]), route=[1, 3, 2] → [-1]
Узел 3 — ребёнок узла 2, поэтому в любом обходе он идёт после 2. Маршрут недостижим: [-1].
root=tree_node([2, 1, 3]), route=[2, 1, 3] → []
Обход уже совпадает с маршрутом — ничего менять не нужно.
n, все разныеroute — перестановка чисел от 1 до nroot=tree_node([1, 2, 3, 4]), route=[1, 3, 2, 4]
[1]
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 82 теста на сервере, включая скрытые.