树dfs算法的空间复杂度

Question

我正在评估以下算法的空间复杂度，以反转一棵树：

public TreeNode invertTree(TreeNode root) {
    if (root == null) {
        return null;
    }
    TreeNode right = invertTree(root.right);
    TreeNode left = invertTree(root.left);
    root.left = right;
    root.right = left;
    return root;
}

我知道空间复杂度是调用堆栈的次数，它是O(h)，其中h是树的高度。但我的困惑是，在调用堆栈的每个级别，我们都返回一棵树，这会占用一些空间，为什么我们不计算这些空间呢？我认为这是因为树是由函数传入的。但是你如何解释这个空间呢？Java是通过引用传递的，那么在每个调用堆栈级别，引用会占用多少空间？

Answer 1

对象引用所需的空间是恒定的。它不依赖于您所引用的内容。引用树根所需的空间与引用树叶所需的空间相同。

通常，您可以假定每次调用Java中的方法都占用相同数量的堆栈空间。没有办法在堆栈上分配内存(或者，至少现在还没有)。在此方法中，不会在堆上创建或销毁任何对象，因此唯一使用的空间是堆栈帧的空间。