Преобразование двоичного дерева в его зеркальное дерево

Имея бинарное дерево, преобразуйте его в зеркальное дерево.

Зеркало дерева: Зеркало бинарного дерева T — это еще одно бинарное дерево M(T), в котором левые и правые дочерние элементы всех нелистовых узлов переставлены местами. Перед прочтением этой статьи посетите обход порядкового уровня.

Алгоритм — зеркало (дерево): рекурсивный

(1)  Call Mirror for left-subtree    i.e., Mirror(left-subtree)
(2)  Call Mirror for right-subtree  i.e., Mirror(right-subtree)
(3)  Swap left and right subtrees.
          temp = left-subtree
          left-subtree = right-subtree
          right-subtree = temp

В этом подходе учитываются два аспекта. Во-первых, функция зеркала отслеживает узлы, которые являются листовыми узлами, и это делается системным стеком. т. е. когда условие node равно null, должно быть выполнено, системный стек просто отбрасывает его.

теперь оба дочерних узла узла 2 меняются местами. обмен 3, 4 и 5 не производился, потому что они были конечными узлами.

Вывод:

Inorder traversal of the constructed tree is 
4 2 5 1 3 
Inorder traversal of the mirror tree is 
3 1 5 2 4

Сложности времени и пространства: эта программа похожа на обход дерева, а временные сложности будут такими же, как обход дерева, который составляет O (n)

СПОСОБ 2. Обход предварительного заказа (простой!:)

Подход:

  • Выполните предварительный заказ.
  • Начиная с корня, поменяйте местами левого и правого дочерних элементов.
  • Рекурсивно вызовите одну и ту же процедуру в левом и правом поддеревьях.

Вывод:42513 Зеркальное отображение: 31524

Сложность времени: o(n), так как обе операции выполняются в одно и то же время, и обе требуют одинакового пространства.

находите все больше и больше полезных ресурсов, связанных с #ai #machinelearning #deeplearning #python… https://twitter.com/Ajinkya_Tweets

Аджинкья Джавале, https://www.linkedin.com/in/ajinkya-jawale-b3421a12a/

https://angel.co/ajinkya-jawale

связаться со мной здесь, [email protected]

спасибо!