В худшем случае, сложность пространства при обходе двоичного дерева предварительного порядка с использованием итеративной и рекурсивной реализации

Question

Учитывая сложность пространства в худшем случае полностью перекошенного дерева (по сути, связанного списка) с использованием приведенной ниже итеративной и рекурсивной реализации:

# Iterative
def preorderTraversal(self, root):
    if root is None:
        return []

    stack = [root]

    while stack:
        root = stack.pop()

        print root.val

        if root.right:
            stack.append(root.right)
        if root.left:
            stack.append(root.left)

# recursive
def preorderTraversal(self, root):
    if not root:
        return

    print(root.val)
    preorderTraversal(root.left)
    preorderTraversal(root.right)

• Итеративный - в каждой итерации ровно один узел выталкивается, а один узел выдвигается, так что в стеке всего один oop. Это O (1)
• Recursion - поскольку ему необходимо поддерживать стек вызовов, который содержит все узлы, когда код достигает конечного узла. Это O (n)

Вопросы:

1. Правильно ли мое понимание выше?
2. Если так, почему у нас есть разница в пространстве между итеративной и рекурсивной реализациями для худшего случая? Они оба основаны на стеке, поэтому, на мой взгляд, во всех случаях у них одинаковая сложность времени и пространства. В чем причина такой разницы?
3. Есть ли способ реализовать итеративное решение, которое во всех случаях точно соответствует рекурсивной версии с точки зрения сложности пространства?

Заранее спасибо!

Answer 1

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

Answer 2

Правильно ли мое понимание выше?

Учитывая случай, когда заполнены только узлы left (или right, если мы не учитываем хвостовую оптимизацию), ваше понимание верно, но такое полностью перекошенное дерево не является худшим случаем для итеративной реализации. Там с таким деревом, как

    0
    ^
   1 8
   ^
  2 7
  ^
 3 6
 ^ 
4 5

, stack вырастает примерно до n / 2 .