data-structures - 为什么递归中序遍历的空间复杂度是 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

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