创建递归对象的空间复杂性

Question

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

请注意：

1. 我不需要改进/修改我的代码的建议。下面的代码示例是针对我的问题量身定做的。
2. 还有，please ignore space-complexity adding stack frames。我正在寻找创建的数字'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

在我看来，空间复杂度是O(1)，因为在每个堆栈帧弹出之后，在该堆栈帧上创建的对象的引用将丢失并垃圾收集。我说得对吗？

不，你的假设是错误的。雷·图尔解释得很好。在递归的任何一点上，您都必须计算存储到内存中的所有内部堆栈帧，因为空间复杂性考虑了所有辅助空间(额外的空间)以及输入(这里没有强调)。

下一首,

我正在寻找创建的数字'TreeData‘对象的空间复杂性。

递归程序占用的最大空间是到递归树最大深度的比例。递归树的最大深度定义为树中最长路径的长度。

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

在我看来，在任何时候都只有3个TreeData对象。这就是我想要证实的。

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

Answer 2

这里不使用尾递归，而是在递归树时构建堆栈帧。公平地说，数一数那些堆栈帧。如果您的树是平衡的，那么您将在递归时生成log n堆栈帧。在最坏的情况下，如果使用完全退化的树，则可能有最多n个堆栈帧。

Answer 3

但是，在每个递归中，它都会创建TreeData对象。

不是这样的。只在递归的基本情况下创建新的TreeData对象。如果您关心这个问题，为什么不只在类中声明一个静态的最后TreeData实例一次，您可以使用它。毕竟，从这个节点传播回来的唯一东西是isBalanced布尔值。

如果将方法签名更改为返回布尔值，还可以直接传播布尔值。