root двоичного дерева. Перестройте дерево в цепочку из тех же узлов:
- у каждого узла левая ссылка left равна None;
- правая ссылка right ведёт к следующему узлу цепочки, у последнего — None;
- узлы идут в порядке прямого обхода (preorder): сначала узел, затем его левое поддерево, затем правое.
Переставляйте ссылки существующих узлов, а не создавайте новые, и верните голову цепочки — прежний корень (для пустого дерева — None).
Попробуйте обойтись O(1) дополнительной памяти.root=tree_node([7, 3, 9, 1, None, None, 4]) → [7, None, 3, None, 1, None, 9, None, 4]
Прямой обход: 7, 3, 1, 9, 4. После вызова дерево — цепочка 7 → 3 → 1 → 9 → 4 по правым ссылкам, все левые ссылки None.
root=tree_node([5, 2, None, -6]) → [5, None, 2, None, -6]
Дерево уходит влево: 5 → 2 → -6. Узлы переезжают направо, получается цепочка 5 → 2 → -6.
root=tree_node([]) → None
Пустое дерево — менять нечего.
root=tree_node([7, 3, 9, 1, None, None, 4])
[7, None, 3, None, 1, None, 9, None, 4]
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 34 теста на сервере, включая скрытые.