СегодняТемы LeetCodeВ 60-й статье мы рассмотрим 94 вопроса LeetCode, упорядоченный обход бинарного дерева.
Официальная сложность этого вопросаMedium, 3304 лайка, всего 140 дизапов, а проходимость 63,2%, что очень много среди тем Medium. Этот вопрос очень простой, и можно сказать, что это один из вопросов по алгоритмам, которые должны знать программисты.
Сначала рассмотрим значение.
смысл названия
Смысл вопроса очень короткий, всего одно предложение: задано бинарное дерево, вернуть результат его обхода по порядку.
Образец
Input: [1,null,2,3]
1
\
2
/
3
Output: [1,3,2]
Решить эту задачу с помощью рекурсии очень просто.Может ли рекурсияПойми?
отвечать
Давайте сначала представим обход по порядку двоичного дерева, Существует три способа обхода двоичного дерева, а именно:Предзаказ, заказ и постзаказ. Новичкам может показаться, что эти три последовательности глупы и непонятны, и вы не знаете, в чем между ними разница. На самом деле, это очень просто сказать прямо: метод обхода на самом деле относится кПорядок выбора при рекурсивном обходе.
Предположим, что узел, к которому мы возвращаемся, — это u, у которого есть левый и правый дочерние элементы. При предположении, что левый ребенок должен посетить перед правым ребенком, у нас есть три стратегии. Первый состоит в том, чтобы сначала добавить u в последовательность доступа, а затем обойти левое и правое поддеревья по отдельности, а второй — рекурсивно пройти по левому поддереву, затем добавить u в последовательность доступа и, наконец, пройти по правому поддереву. Третья стратегия заключается в рекурсивном обходе левого и правого поддеревьев и, наконец, добавлении u в последовательность доступа.
В чем разница между этими тремя стратегиями? На самом деле, самая большая разница в том, чтоПорядок, в котором u добавляется в последовательность доступа, отличается, если сначала добавляется u, а затем осуществляется доступ, то это предварительный заказ. Если сначала посещается левое поддерево, а затем добавляется u, то это неупорядоченный порядок, а если левое и правое поддеревья рекурсивно посещаются первыми, а u добавляется последним, то это обратный порядок. Проще говоря, первое соединение — это предварительный заказ, среднее соединение — это средний порядок, а последнее соединение — это пост-заказ. Если вы все еще чувствуете себя немного запутанным, давайте взглянем на код, и он будет очень понятен.
# 先序
def dfs(u):
visited.append(u)
dfs(u.left)
dfs(u.right)
# 中序
def dfs(u):
dfs(u.left)
visited.append(u)
dfs(u.right)
# 后序
def dfs(u):
dfs(u.left)
dfs(u.right)
visited.append(u)
Но вопрос требует от нас сделать это без рекурсии, что нам делать?
На самом деле способ есть, нам нуженНачните с реализации принципа рекурсии. Мы знаем, что внутри компилятора, когда мы вызываем другую функцию из одной функции, информация этих функций будет храниться в структуре стека. Каждый узел в середине стека записывает имя функции и место ее выполнения в данный момент, а также некоторые промежуточные переменные и так далее. Поэтому, когда мы рекурсивно, это фактически процесс помещения текущей функции в стек.
Например, наша функция dfs рекурсивно вызывает функцию dfs в строке 5, тогда стек внутри компилятора запишет [(dfs, 5), (dfs, 1)]. Если мы снова вызовем функцию суммы в первой строке dfs, компилятор снова добавит функцию суммы в стек, приняв вид: [(dfs, 5), (dfs, 1), (sum, 1)]. Когда функция завершит выполнение, она будет извлечена из стека.
короче,Рекурсия фактически использует структуру стека, поддерживаемую компилятором, для упрощения написания нашего кода и функций.. Поскольку этот вопрос требует, чтобы мы не использовали рекурсию, мы можем использовать стек только для имитации этого процесса. Поскольку нам нужно самим поддерживать элементы в стеке, весь процесс будет немного сложнее.
В этой задаче мы используем стек для отслеживания узлов в дереве. Узел на вершине стека является текущим посещаемым узлом.
# Definition for 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 inorderTraversal(self, root: TreeNode) -> List[int]:
ret = []
stack = []
stack.append(root)
while len(stack) > 0:
# 获取栈顶顶点
cur = stack[-1]
if cur is None:
stack.pop()
continue
# 如果左孩子存在，那么优先遍历左孩子
if cur.left is not None:
stack.append(cur.left)
# 把左指针置为空，防止死循环
# 这里也可以用set来维护
cur.left = None
continue
# 左边遍历结束之后加入序列
ret.append(cur.val)
stack.pop()
if cur.right is not None:
stack.append(cur.right)
return ret
Суммировать
Если это просто обход бинарного дерева, это может сделать любой, но если вы не можете использовать рекурсию, то это испытание жесткой силы. Нам необходимо иметь глубокое понимание основных принципов рекурсии и быть знакомым с использованием структуры данных стека. Логику этого кода понять несложно, а вот реализация достаточно утомительна, всем рекомендую попробовать.
Сегодняшняя статья здесь, если вам понравилась эта статья, пожалуйста, приходите на волнукачество три, поддержите меня (Подписывайтесь, делайте репосты, лайкайте).
Оригинальная ссылка, обратите внимание
- END -