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

Посмотрел в инете код инвертирования бинарного дерева. Но я не мог, что он делает. Он написан на Python. Я сам программист на питоне, но не мог этого понять.

Фрагмент выглядит следующим образом:

def invertTree(root):
    if root:
        root.left, root.right = invertTree(root.right), invertTree(root.left)
        return root

Я не понимаю этого root.left и root.right . Корень — это главный узел в графе, это будет целое число или одиночный символ. Но что представляет собой root.left в Python? Я честно не понимаю.

Обновлять:

Насколько я понимаю, узел - это доступ, как показано ниже:

class Node:
   def __init__(self, data):
      self.left = None
      self.right = None
      self.data = data
   def PrintTree(self):
      print(self.data)

root = Node(10)
root.PrintTree()
root может быть узлом, у которого есть int для его .value или как там называется атрибут value, но это точно не int сам по себе — попробуйте запустить type(root) и посмотрите, каков его фактический тип. Могу поспорить, что это что-то вроде Node(), и здесь происходит то, что эта функция просто меняет местами .left и .right для узла, а затем продолжает делать то же самое для обоих поддеревьев, эффективно «инвертируя» дерево.
Grismar 21.11.2022 06:45

Неясно. Вы смотрите на это? Пример кода в этой статье определяет класс Node и создает экземпляры класса Node. Что именно ты не понимаешь?

relent95 21.11.2022 10:26

Это все еще неясно. Попытайтесь понять эти понятия: класс Python, Python __init__, переменные экземпляра Python, экземпляры Node, ссылки на левый и правый дочерние узлы, двоичное дерево. Похоже, вы не можете ЯСНО описать, в чем ваша проблема, потому что вы не понимаете этих понятий.

relent95 22.11.2022 08:26

Каждое решение, которое я видел для инвертирования двоичного дерева, это всего 4 строки кода рекурсии, но я не понимаю, что происходит под капотом. Я думал, что мы должны сначала представить двоичное дерево, используя классы и функцию инициализации. Но в leetcode нет никакого класса для представления узла. Есть только класс и функция для написания кода.

Reactoo 22.11.2022 09:41

Смотрите мой ответ. Это лучшее, что я могу сказать.

relent95 22.11.2022 16:40
Мутабельность и переработка объектов в Python
Мутабельность и переработка объектов в Python
Объекты являются основной конструкцией любого языка ООП, и каждый язык определяет свой собственный синтаксис для их создания, обновления и...
Другой маршрут в Flask Python
Другой маршрут в Flask Python
Flask - это фреймворк, который поддерживает веб-приложения. В этой статье я покажу, как мы можем использовать @app .route в flask, чтобы иметь другую...
14 Задание: Типы данных и структуры данных Python для DevOps
14 Задание: Типы данных и структуры данных Python для DevOps
Проверить тип данных используемой переменной, мы можем просто написать: your_variable=100
Python PyPDF2 - запись метаданных PDF
Python PyPDF2 - запись метаданных PDF
Python скрипт, который будет записывать метаданные в PDF файл, для этого мы будем использовать PDF ридер из библиотеки PyPDF2 . PyPDF2 - это...
Переменные, типы данных и операторы в Python
Переменные, типы данных и операторы в Python
В Python переменные используются как место для хранения значений. Пример переменной формы:
Почему Python - идеальный выбор для проекта AI и ML
Почему Python - идеальный выбор для проекта AI и ML
Блог, которым поделился Harikrishna Kundariya в нашем сообществе Developer Nation Community.
1
5
109
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

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

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

Я добавил свой код в раздел обновлений. Я думал, что доступ к корневому узлу осуществляется из самого себя из init, который находится в том же классе. Но вы ставите два класса. Как получить доступ к корню из другого класса. Я не понимаю.

Reactoo 22.11.2022 00:35

Я также добавил основную функцию в свой обновленный раздел..! если вы все же хотите глубже понять, например, код inorderTraversal или как реализовать инициализацию двоичного дерева.. вы можете увидеть код драйвера. Я дал ссылку, вы можете просто войти и закодировать ее также для лучшего понимания

Yash Mehta 22.11.2022 06:46
Ответ принят как подходящий

Двоичное дерево можно использовать для хранения элементов, отсортированных по ключу. (Для более сложной темы ищите сбалансированное двоичное дерево.) Если элементы отсортированы в порядке возрастания, для любого поддерева 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() было отсортировано в порядке возрастания. После вызова он будет отсортирован в порядке убывания. Вот почему операция называется «инверсия».

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

Спасибо, Релент, ваш ответ намного понятнее, чем те видео на YouTube. Но последнее, что я должен спросить у вас, — должны ли мы каждый раз получать информацию от пользователя для этого или отправлять список? Кроме того, в leetcode эта функция инициализации внутри другого класса закомментирована, тогда как код запускается, если инициализация закомментирована ?? Пожалуйста, дай мне знать.

Reactoo 22.11.2022 20:20

Онлайн-судья Leetcode не имеет открытого исходного кода. Насколько я знаю, они запускают представленный код (решение) в своей собственной структуре, которая должна содержать определение класса TreeNode и код инициализации дерева.

relent95 23.11.2022 05:52

Другие вопросы по теме