Преобразование двоичного дерева в его зеркальное дерево
Имея бинарное дерево, преобразуйте его в зеркальное дерево.
Зеркало дерева: Зеркало бинарного дерева 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]
спасибо!