Напишите функцию, которая принимает двоичное дерево и заменяет каждый левый узел в дереве соответствующим правым узлом.
мы должны переставить каждый узел на его относительную противоположную сторону, мы могли бы просто рекурсивно вызывать функцию перестановки во всех узлах левого и правого узлов, пока не достигнем конца дерева.
Функция swap заменяет левый узел правым и правый узел левым узлом.
Как только мы достигаем узла, мы сначала вызываем функцию подкачки, а затем рекурсивно вызываем вспомогательную функцию для обоих его дочерних узлов, пока она не равна None.
В базовом случае рекурсия прерывается, когда дочерние узлы Left и Right текущего узла имеют значение None.
Мы добавили простую функцию печати для проверки значений узла до и после инвертирования двоичного дерева.
Код доступен здесь.
Временная сложность составляет O(n), где n — количество входных узлов в двоичном дереве.
Сложность пространства составляет O(d), где d — это глубина самой длинной ветви во входном Дереве.
