Итеративное решение для обхода двоичных деревьев с предварительным упорядочиванием в Python3

Двоичные деревья — это иерархические структуры данных, в которых каждый родительский узел имеет не более 2 дочерних узлов. В сегодняшней статье мы рассмотрим важную тему, которая встречается на многих собеседованиях по техническому кодированию.

ПОСТАНОВКА ЗАДАЧИ: Задав корень двоичного дерева, вернуть обход значений его узлов в предварительном порядке. Предоставьте итеративное решение вместо рекурсивного.

РЕШЕНИЕ:

Предварительный обход двоичного дерева происходит в таком порядке:

  • Сначала посещается корень
  • Обход левого поддерева
  • Обход правого поддерева

Для того чтобы решить эту задачу итеративным способом, нам потребуется реализовать структуру данных Stack. Это нелинейная структура данных, в которой операции выполняются в порядке LIFO (Last In First Out). Подход к нашему ответу прост и будет заключаться в следующем:

  • Мы инициализируем два списка, т.е. один для переноса вывода, а другой для работы в качестве структуры данных стека. Стек будет инициализирован корневым значением двоичного дерева.
  • Затем мы выполним цикл while на нашем стеке до тех пор, пока он имеет значение. В цикле будут выполняться следующие операции по порядку:
  • Удалить (pop) самое верхнее значение (корневой узел) в стеке и добавить его в выходной список
  • Вставьте правое дочернее значение вытолкнутого значения в стек
  • Вставьте левое дочернее значение вытолкнутого значения в стек.
  • Вернуть выходной список в конце цикла.

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

Важно отметить, что сначала в стек помещается правый дочерний элемент, а затем левый. Это связано с LIFO-природой стека. Это позволит нам получить доступ сначала к левому дочернему элементу, а затем к правому.

БОЛТОВНЯ СТОИТ ДЕШЕВО, ПОКАЖИТЕ МНЕ КОД:

# Definition of a Binary Tree node
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        output, nodestack = [], [root]
        while nodestack:
            node = nodestack.pop()
            if node:  # preorder: root -> left -> right
                output.append(node.val)
                nodestack.append(node.right)
                nodestack.append(node.left)
        return output
Вход в полноэкранный режим Выход из полноэкранного режима

Если эта статья была полезной, пожалуйста, ставьте лайк и подписывайтесь на мою рассылку, чтобы получать больше материалов по DSA в Python.

Оцените статью
devanswers.ru
Добавить комментарий