algorithm - 递归创建对象的空间复杂度

Question

如果树是平衡的，则下面代码中的

checkIfBalanced() 方法返回 true，否则返回 false。但是在每次递归中它都会创建 TreeData 对象。在我看来，空间复杂度为 O(1)，因为在弹出每个堆栈帧后，在该堆栈帧上创建的对象的引用将丢失并被垃圾收集。 我对吗 ？

请注意:

1. 我不是在寻求改进/更改我的代码的建议。以下代码示例是为回答我的问题而量身定制的。

2. 此外，请忽略空间复杂性添加堆栈帧。我正在寻找创建的数字“TreeData”对象的空间复杂度。在我看来，在任何时候都只有 3 个 TreeData 对象。这就是我要验证的。谢谢。

   private static class TreeData {
        private int height;
        private boolean isBalanced; 

        TreeData(int height, boolean isBalanced) {
            this.height = height;
            this.isBalanced = isBalanced;
        }
    }

    public boolean checkIfBalanced() {
        if (root == null) {
            throw new IllegalStateException();
        }
        return checkBalanced(root).isBalanced;
    }

    public TreeData checkBalanced(TreeNode node) {
        if (node == null) return new TreeData(-1, true);

        TreeData tdLeft = checkBalanced(node.left);
        TreeData tdRight = checkBalanced(node.right);

        if (tdLeft.isBalanced && tdRight.isBalanced && Math.abs(tdLeft.height - tdRight.height) <= 1) {
            return new TreeData(Math.max(tdLeft.height, tdRight.height) + 1, true);
        } 

        return new TreeData(Math.max(tdLeft.height, tdRight.height) + 1, false);
    }

Answer 1

In my opinion space complexity is O(1) as after each stack frame is popped, the reference of the object created on that stack frame is lost and garbage collected. Am I right ?

不，你的假设是错误的。 Ray Toal 对此做了非常漂亮的解释。在递归的任何时候，您都必须计算所有保存到内存中的内部堆栈帧，因为空间复杂度考虑了所有辅助空间(额外空间)以及输入(此处未强调)。

接下来，

I am looking for space complexity of number 'TreeData' objects created.

递归程序消耗的最大空间与构成递归树的最大深度成比例。递归树的最大深度定义为树中最长路径的长度。

对于给定的程序，程序将从树的根开始，首先开始创建左子树，然后检查右子树。最后，它会返回最长路径的长度以及树是否平衡。

It looks to me that at any point there would be only 3 TreeData objects. That's what I want to verify.

不是，在任何特定的执行时间，首先验证所有的左子树，然后验证右子树，所以内存中的 TreeData 对象数将只有 1。每次都会检查它的左子树或正确的 child 。因此，所有这些(log n --- 在平衡树的情况下，或 n --- 在退化树的情况下)节点除了一个将继续堆叠在内存中。在特定的时刻，只有 1 个 TreeData 对象处于事件状态，其他的将暂停并堆叠在内存中等待轮到它们弹出。