验证二叉搜索树的空间复杂性

Question

验证二叉树是否为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).