使用迭代和递归实现的二叉树遍历的最坏情况空间复杂度

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)

• 迭代-在每次迭代中，恰好弹出一个节点，并推送一个节点，因此在整个循环中堆栈只有一个节点。这是O（1）
• 递归-因为当代码到达叶节点时，它需要维护包含所有节点的调用堆栈。这是O（n）

以上我的理解正确吗？如果是这样，为什么在最坏的情况下，迭代和递归实现之间的空间差异呢？它们都是基于堆栈的，因此直觉上我认为它们在所有情况下都具有相同的时间和空间复杂性。是什么真正导致了这种差异？

提前感谢！

Answer 1

我以上的理解正确吗？

Answer 2

您的理解是正确的。即使两个版本都使用堆栈，它们使用的方式也有所不同。您不能比较

堆栈的数据结构

和调用的堆栈