为什么递归inorder的空间复杂度遍历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）。

我错过了什么？

Answer 1

返回时，地址将从堆栈中删除。从靠近根的级别进行新呼叫时，将重新使用此空间。因此，堆栈上的最大内存地址数是树高。

Answer 2

恕我直言，你应该把空间复杂性视为O(n)。在处理Big 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)空间复杂性同样正确。