为什么递归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)只是在输入元素数量方面为我们提供了一种统一的思维方式。虽然，O(h)由于@StefanHaustein 在他的回答中提到的原因，空间复杂度同样是正确的。