validation二叉搜索树的空间复杂性

validation二叉树是否为BST的最佳算法如下

IsValidBST(root,-infinity,infinity); bool IsValidBST(BinaryNode node, int MIN, int MAX) { if(node == null) return true; if(node.element > MIN && node.element < MAX && IsValidBST(node.left,MIN,node.element) && IsValidBST(node.right,node.element,MAX)) return true; else return false; } 

这个逻辑的空间复杂度显然是O(logN) ，我假设它是递归的代价。 价值是如何达到的？

Answer 1

我的评论升级为回答：

除了方法变量和返回值之外，没有使用其他数据，所以实际上，所有内存都是“递归成本”。 因此，总成本将与树的深度成线性比例。

在平衡二叉搜索树中 ，深度为O(log n) ，因此实际上，空间复杂度也是O(log n) 。 但是，一般来说BST不一定是平衡的，它甚至可以是长度为n的链，如果根是最小的，它的右子是第二个最小的元素，依此类推。 在这种情况下，此递归的空间复杂度为O(n) 。