Инвертировать двоичное дерево в python с рекурсией

Сначала поймите проблему с диаграммой ..!

Q:- Учитывая бинарное дерево, вы должны преобразовать бинарное дерево в инвертированное бинарное дерево. Схема

Class TreeNode: {Инициализация бинарного дерева}

Ключевым моментом здесь является понимание того, что для инвертирования двоичного дерева нам нужно только рекурсивно поменять местами дочерние элементы. Чтобы избежать использования переменной tmp, мы можем сделать это с помощью python, воспользовавшись упаковкой и распаковкой кортежей Python и выполнив прямую замену:

> class TreeNode:
>      def __init__(self, val=0, left=None, right=None):
>          self.val = val
>          self.left = left
>          self.right = right

> class Solution:
>     def invertTree(self, root):
>         if root:
>             root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
>         return root

Обратите внимание, что если один из дочерних элементов имеет значение null, условие root не будет запущено, и обмен на верхнем уровне все равно будет выполняться (например, узел имеет правый дочерний элемент, но не имеет левого дочернего элемента, присвоение будет root.left, root. право = корень.право, ноль).

Что делает root.left? Обход левого поддерева бинарного дерева

Что делает root.right? Обход правого поддерева бинарного дерева.

Примечание. Вы можете получить доступ к значениям root с помощью root.val, поскольку вы видите класс TreeNode. Я сохранил значение в val*

Также, чтобы узнать больше об основных вопросах бинарных деревьев, вы должны ответить.

(1) Обход предзаказа

(2) Неупорядоченный обход

(3) Обход почтового заказа

Обновлен раздел.!

В-: Как получить доступ к корню из другого класса?

A-: Просто вызовите его в основной функции..!

Основная функция

> if __name__ = "__main__":
>     s=input()
>     root=TreeNode(s)   
>     Solution().invertTree(root) 
>     inorderTraversal(root) # You can print in any other traversal also as the testcases requirements

Подробнее см. в коде драйвера (начиная с 18-й строки {Below Link}): https://practice.geeksforgeeks.org/problems/mirror-tree/1

Двоичное дерево можно использовать для хранения элементов, отсортированных по ключу. (Для более сложной темы ищите сбалансированное двоичное дерево.) Если элементы отсортированы в порядке возрастания, для любого поддерева T с корневым узлом R любой элемент в левая ветвь R должна быть меньше любого элемента правой ветви R.

Это сильно измененная версия примера кода из Инвертировать бинарное дерево Шивали Бхадания.

'''
         5                         5
       /   \                     /   \
      /     \                   /     \           
     3       7    =======>     7       3           
    / \     /                   \     / \
   1   4   6                     6   4   1 
'''
class Node:
    def __init__(self, data):
        self.left = self.right = None
        self.data = data
    def __repr__(self):
        return repr(self.data)

def invert(root):
    left, right = root.left, root.right
    print(['visiting', root, 'swapping', left, right])
    root.left, root.right = right, left
    if left: invert(left)
    if right: invert(right)

root = Node(5)
root.left = node3 = Node(3)
root.right = node7 = Node(7)
node3.left = Node(1)
node3.right = Node(4)
node7.left = Node(6)

invert(root)

Это выведет следующее.

['visiting', 5, 'swapping', 3, 7]
['visiting', 3, 'swapping', 1, 4]
['visiting', 1, 'swapping', None, None]
['visiting', 4, 'swapping', None, None]
['visiting', 7, 'swapping', 6, None]
['visiting', 6, 'swapping', None, None]

В приведенном выше примере дерево перед вызовом invert() было отсортировано в порядке возрастания. После вызова он будет отсортирован в порядке убывания. Вот почему операция называется «инверсия».

Вы можете понять, почему простая рекурсия замены левого дочернего элемента и правого дочернего элемента приводит к инверсии, путем имитации приведенного выше примера кода с помощью карандаша и бумаги вручную. Сравните журналы с вашим расчетом.