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

Question

所以我知道 space 递归顺序遍历的复杂度是 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 个内存地址推送到调用堆栈，因此，space 复杂度应该是 O(n)。

我错过了什么？

Answer 1

返回时从堆栈中删除地址。当从更接近根的级别进行新调用时，将重新使用此 space。所以同时入栈的内存地址的最大个数就是树高

Answer 2

恕我直言，您应该将 space 复杂度视为 O(n)。在处理 Big O 表示法中的 space 和时间复杂度时，我们总是尝试将复杂度值作为输入元素数量的函数，在这种情况下为 n。

此外，如果您考虑右偏二叉树或左偏二叉树的情况，您会发现这种 O(n) space 复杂度是合适的。看看下面的右偏二叉树的例子：

节点数，n = 3

递归遍历需要的栈帧数=3

节点数，n = 4

递归遍历需要的栈帧数=4

因此您可以得出结论，O(n) 是最坏情况下的 space 复杂度（w.r.t。树结构）。在所有其他 cases/types 树中，所需的堆栈帧数总是少于 n。这就是我们表达复杂性的方式。所有可能情况下的实际 space 应始终小于或等于描述的函数。

另外，在所有情况下它总是 O(h) <= O(n)。因此，将 space 复杂度视为 O(n) 只是为我们提供了一种在输入元素数量方面的统一思维方式。虽然，由于@StefanHaustein 在他的回答中提到的原因，O(h) space 复杂性同样正确。

Answer 3

Space递归的复杂度永远是递归的高度/递归深度，所以遵循这个一般规则，中序遍历最多可以有h个高度，其中h是从根开始的最深节点的长度。 Space 递归的复杂度 = O(递归树的深度)。

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

Why is the space complexity of a recursive inorder traversal O(h) and not O(n)

binary-tree

traversal

inorder

data-structures