Python инвертировать бинарное дерево

инвертировать двоичное дерево в 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 для узла, а затем продолжает делать то же самое для обоих поддеревьев — эффективно » инвертирование» дерева.

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

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

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

2 ответа

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

Это сильно измененная версия кода примера на странице Invert a Binary Tree Шивали Бхадания. .

''' 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 эта функция инициализации внутри другого класса закомментирована, тогда как код запускается, если инициализация закомментирована ?? Пожалуйста, дай мне знать.

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

Вопрос: Данный бинарное дерево необходимо преобразовать в инвертированное бинарное дерево. Диаграмма

Ключевым моментом здесь является понимание того, что для инвертирования двоичного дерева нам нужно только рекурсивно поменять местами дочерние элементы. Чтобы избежать использования переменной 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.right = root.right, null).

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

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

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

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

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

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

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 

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

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

Источник

How to Reverse a Binary Tree in Python

Reversing a Binary Tree is a common programming interview question.

By learning how to Reverse a Binary Tree in Python, you are working towards fundamental data structure algorithms commonly found in Computer Science degrees and across the industry.

If we take a look at the following Data Tree Image, we will notice a few common points.

Firstly, a binary tree simply means a tree that contains between 1 and 2 child nodes.

Each node can be represented in code as follows:

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

The goal of this exercise is to invert or reverse the order of these nodes. This is actually as simple as swapping left and right nodes with one another where applicable.

To do this, we will create a function called invertTree that will take in each node as an argument.

We first check to see if the node exists and if it does, we simply swap it’s left and right nodes with one another. Then we recursively attempt to invert each leg and finally return the node.

def invertTree(node): if node is None: return None node.left, node.right = node.right, node.left invertTree(node.left) invertTree(node.right) return node 

This is all the code that is needed to perform the inversion.

We also need to initiate the data so that we can run some tests.

sample_tree = TreeNode(1) sample_tree.left = TreeNode(2) sample_tree.right = TreeNode(3) sample_tree.left.left = TreeNode(4) sample_tree.left.right = TreeNode(5) sample_tree.right.left = TreeNode(6) sample_tree.right.right = TreeNode(7) 

The above code creates a tree as per our initial illustrations above.

How do we know if our code was successful though? We will need some way to print this tree structure out and compare it both pre and post inversion.

def printTree(node): print(node.val, end="") if node.left: printTree(node.left) if node.right: printTree(node.right) 

The above code takes in the root node of our tree, and recursively prints each left and right node if available.

//print our initial structure printTree(sample_tree) //add a line break print() //create our inverted tree and print it inverted_tree = invertTree(sample_tree) printTree(inverted_tree) 

This will result in the following output, which matches the two illustrations we preempted.

Top Related Articles

1. How to delete a file in Python
2. When to use Pip3 instead of Pip in Python
3. How to Package a Python App using Nuitka
4. When your Python code is much faster with PyPy
5. Introduction to PIP – Python Package Manager
6. How to Setup and Use the Python Virtual Environment
7. Multiprocessing in Python3
8. Counting in Python using a list
9. [Solved] Pip: There was a problem confirming the ssl certificate
10. How to Learn Python Programming Quickly

Источник

Инвертировать альтернативные уровни идеального бинарного дерева

Напишите эффективный алгоритм инвертирования альтернативных уровней идеального бинарного дерева.

Например, рассмотрим следующее дерево:

Мы должны преобразовать его в следующее дерево:

1. Использование обхода по уровням

Идея состоит в том, чтобы выполнить обход порядка уровней идеального бинарного дерева и последовательно обходим его узлы. Затем для каждого нечетного уровня поместите все узлы, присутствующие на этом уровне, в stack. Наконец, в конце каждого нечетного уровня мы помещаем узлы, присутствующие в stack, в их правильное положение. Ниже приведена программа на C++, Java и Python, которая демонстрирует это:

C++

результат:

1 3 2 4 5 6 7 15 14 13 12 11 10 9 8

Java

результат:

1 3 2 4 5 6 7 15 14 13 12 11 10 9 8

Python

результат:

1 3 2 4 5 6 7 15 14 13 12 11 10 9 8

Временная сложность приведенного выше решения равна O(n) , куда n это общее количество узлов в бинарном дереве. Программа требует O(n) дополнительное пространство для хранения узлов, присутствующих на нечетных уровнях двоичного дерева. Stack предпочтительнее списка для хранения узлов, поскольку это структура данных LIFO, и нам не нужно реверсировать ее перед присвоением значения узлам.

2. Использование обхода по порядку

Идея остается похожей на предыдущий подход, за исключением того, что здесь мы рекурсивно обходим дерево в мода, и узлы хранения представляют все нечетные уровни в stack и заменяют их позже, выполняя другой неупорядоченный обход. Этот подход демонстрируется ниже на C++, Java и Python:

Источник