为何平衡树场景下该BST验证算法时间复杂度为O(n)？

我尝试编写一个算法，用于判断给定的完全二叉树是否为二叉搜索树（BST），要求算法的时间复杂度为O(n)，其中n为树的节点总数。

我提出了如下解决方案（伪代码）：

def isBST(x):
    if x=NIL: return True
    if min(x.right) < x.value or max(x.left) > x.value: return False
    isBST(x.left)
    isBST(x.right)
    return True

其中min(x.right)表示x的右子树中的最小值，对应实现如下：

def min(x):
    while x.left:
        x = x.left
    return x.value

max(x.left)则用于获取x的左子树中的最大值。

我在网上看到，这类解决方案在平衡/满树场景下的时间复杂度为O(n)，对应的递归式为：

T(n) = T(n/2) + O(logn)

请问该递归式对应的时间复杂度确实是O(n)吗？若是，原因是什么？若不是，该如何将算法优化至O(n)时间复杂度？

关于递归式的时间复杂度结论 #

你提到的递归式T(n) = T(n/2) + O(logn)对应的时间复杂度不是O(n)，而是O((logn)²)。可以用两种方式验证：

1. 递归树分析：每一层递归的时间代价是O(logn)，而平衡树的递归深度是O(logn)，总时间就是各层代价的总和：O(logn) * O(logn) = O((logn)²)。
2. 主定理推导：主定理中，此递归式属于a=1, b=2, f(n)=O(logn)的情况，由于n^log_b a = 1，而f(n)的增长速度比1快但未达到多项式级，因此时间复杂度为O((logn)²)。

不过这里要纠正一个误解：你的原算法是同时递归左右子树，真实的递归式应该是T(n) = 2T(n/2) + O(logn)。用主定理分析这个式子：a=2, b=2, n^log_b a =n，而f(n)=O(logn)的增长速度远慢于n，因此平衡树场景下时间复杂度是O(n)——但这只是理想情况，在非平衡的完全二叉树（比如左斜树）中，原算法的时间复杂度会退化到O(n²)，因为每个节点找左子树最大值时都会重复遍历整个左子树，产生大量冗余操作。

优化到严格O(n)时间的方案 #

原算法的问题在于重复遍历子树获取min/max，优化的核心是递归时传递当前节点的合法取值范围，避免重复遍历：

def isBST(x, lower_bound=-∞, upper_bound=+∞):
    if x == NIL:
        return True
    # 当前节点值必须在[lower_bound, upper_bound)范围内（可根据BST定义调整开闭区间）
    if x.value <= lower_bound or x.value >= upper_bound:
        return False
    # 左子树的所有节点必须小于当前节点值，上界设为当前节点值
    left_ok = isBST(x.left, lower_bound, x.value)
    # 右子树的所有节点必须大于当前节点值，下界设为当前节点值
    right_ok = isBST(x.right, x.value, upper_bound)
    return left_ok and right_ok

这个算法中，每个节点只会被访问一次，每次递归仅做O(1)的取值判断，不管树是否平衡，总时间复杂度都是严格的O(n)，完全满足你的要求。

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