为什么递归中序遍历的空间复杂度是O(h)而不是O(n)？

Question

我知道递归中序遍历的空间复杂度是O(h)，而不是O(n)，其中h是树的高度，n是树中节点的数量。

为什么会这样呢？比如说，这是遍历代码：

public void inorderPrint (TreeNode root) {

    if (root == null) {
        return;
    }

    inorderPrint(root.left);
    System.out.println(root.data);
    inorderPrint(root.right);

}

我们将n个内存地址推入调用栈，因此空间复杂度应为O(n)。

我漏掉了什么？

- NotSure

---

你不仅在推入栈中的元素 -- 你还在弹出栈中的元素。因此，某些栈中的部分将被使用多次。树的高度控制了在执行弹出操作之前可以推入多少个元素。顺便说一下 -- 我认为你有一个打字错误，函数应该调用自己而不是 preorderPrint。 - John Coleman

请参考以下链接以获得更清晰的答案：https://dev59.com/6FwX5IYBdhLWcg3wnwnd - Abhijeet Khangarot

Answer 1

返回时，地址从堆栈中移除。当从更接近根的级别发出新的调用时，将重新使用此空间。因此，在同一时间在堆栈上的最大内存地址数是树的高度。

- Stefan Haustein

Answer 2

我认为，你应该将空间复杂度视为O(n)。在处理时间和空间复杂度的大O符号时，我们总是尝试将复杂度值作为输入元素数量的函数给出，这里的输入元素数量是n。

此外，如果考虑右倾二叉树或左倾二叉树的情况，你会发现O(n)的空间复杂度是适合的。请看下面的右倾二叉树的情况：

  1
 / \
    2
   / \
      3

节点数量，n = 3

在递归遍历中需要的堆栈帧数量为3

  1
 / \
    2
   / \
      3
     / \
        4
       / \

节点数量，n = 4

递归遍历所需的堆栈帧数 = 4

因此，可以得出在这种最坏情况下（相对于树结构），O(n)是适合的空间复杂度。在所有其他情况/类型的树中，所需的堆栈帧数始终小于n。这就是我们表达复杂性的方式。所有可能情况占用的实际空间应始终小于或等于所描述的函数。

此外，在所有情况下，O(h) <= O(n)。因此，将空间复杂度视为O(n)只是给我们以输入元素数量的统一思考方式。尽管由于@StefanHaustein在他的答案中提到的原因，O(h)空间复杂度同样正确。

- RBT

---

这肯定取决于你的二叉树的特性。对于一般情况，是的，如果二叉树不平衡，最坏情况下时间复杂度将为O(N)。但如果你确定你的二叉树是平衡的（例如AVL或红黑树），那么你可以保证树的高度最多为Log(N)，因此你的遍历空间复杂度也将为O(log N)。 - Eric Cornelson

Answer 3

递归的空间复杂度总是递归的高度/深度，因此根据这个通用规则，在中序遍历中最多可以有h个高度，其中h是从根节点到最深节点的长度。递归的空间复杂度= O（递归树的深度）。

- Abhijeet Khangarot