以Queue为参数的递归实现空间复杂度分析：验证BST的复杂度是O(N)还是O(NlogN)？

你的O(NlogN)推算存在逻辑误区，当前实现的正确空间复杂度为O(N)，Medium博客的标注是准确的。

你之前的计算思路的核心漏洞 #

你记忆中的「空间复杂度 = 递归深度 * 单次递归占用内存」的公式，仅在一个严格前提下成立：所有递归层级的内存占用完全独立、不跨层共享。这个公式完全没有考虑跨递归层共享的堆上数据结构的开销，甚至会因为错误计算共享对象的内存占用，推导出完全错误的结果。
这里需要明确两个不能混算的空间维度：

• 栈空间：也就是每次递归调用时，在虚拟机栈上分配的栈帧内存，这部分是每层递归独立占用的，量级等于递归深度乘以单帧固定大小
• 堆空间：也就是你在方法内创建的、被所有递归层共享的对象内存，这部分的开销和递归深度无关，只和对象本身存储的数据规模有关

代码实际空间开销拆解 #

你写的实现里，一共只有两类空间开销：

1. Queue的堆内存开销
   这个Queue是在isValidBST方法内只创建一次的实例，在递归调用depth方法时，Java传递的是这个Queue的堆内存引用，不存在每次递归就复制一份完整Queue的情况。
   你的depth方法做的是标准中序遍历，会把整棵树的全部N个节点都加入这个Queue，这部分本身就占O(N)的固定堆空间，和递归深度没有任何关系。
2. 递归栈的内存开销
   每层递归的栈帧只存储当前访问的TreeNode引用、Queue的引用，属于固定大小的内存占用，总开销等于树的高度：
   • 如果是平衡BST，递归深度为O(logN)，这部分开销为O(logN)
   • 如果是斜树（所有节点只有左/右子节点），递归深度为O(N)，这部分开销为O(N)

把两部分开销取最高阶项做加总：

• 哪怕栈空间是O(N)，加上Queue的O(N)堆开销，总空间复杂度还是O(N)
• 哪怕栈空间是O(logN)，Queue的O(N)堆开销依然是主导项

你推导出O(NlogN)的核心错误，是默认每次递归都要持有一份完整的N大小Queue副本，相当于把O(N)的Queue大小乘以了递归深度O(logN)。但实际上全递归过程只有一个Queue实例，根本不存在多份副本的内存消耗。

补充说明 #

如果想把这类BST验证的空间复杂度降到和树高一致的量级（平衡树场景下为O(logN)），完全不需要把中序遍历的全量结果存在Queue/数组里：

• 可以在递归中序遍历的过程中，实时记录上一个访问的节点值，每访问一个新节点就立刻和前值做大小判断，不需要存储全量遍历结果
• 也可以用带上下界的递归判断逻辑，每次递归传入当前节点允许的最小/最大值范围，全程不需要额外的全量数据结构
  这两类实现都可以省掉当前代码里那部分O(N)的Queue堆空间开销。

内容的提问来源于stack exchange，提问作者Sukh