如何用O(nlgn)时间判断二叉树是否为BST？分治法合并设计求助

嘿，这个问题我之前刚琢磨过，咱们一步步把它理明白～

首先得明确：用分治法判断BST，核心不只是每个子树自己是BST，还要保证左子树的所有节点值都小于当前根，右子树的所有节点值都大于当前根。这意味着递归函数不能只返回「是否是BST」这一个布尔值，得额外带回来子树的最大值和最小值——这就是解决你疑惑的关键。

分治法的核心步骤 #

咱们把递归过程拆成三部分：

• 递归处理左子树：得到三个结果：左子树是否为BST、左子树的最小值、左子树的最大值
• 递归处理右子树：同样得到三个结果：右子树是否为BST、右子树的最小值、右子树的最大值
• 合并判断（这一步就是你关心的部分）：
  1. 左、右子树必须都满足是BST
  2. 当前根的值要大于左子树的最大值（如果左子树存在的话）
  3. 当前根的值要小于右子树的最小值（如果右子树存在的话）
     同时，咱们还要计算出当前子树的最小值（左子树最小值和当前根的较小值）和最大值（右子树最大值和当前根的较大值），返回给上层递归用。

关于时间复杂度的澄清 #

你提到的递归式 T(n) = 2T(n/2) + O(n) 其实有点小偏差哦。因为这里的合并步骤根本不需要O(n)的时间——每个节点的合并操作都是**O(1)**的：只需要做几次比较和取最值的操作，完全不需要遍历子树。

正确的递归式应该是 T(n) = T(k) + T(n-k-1) + O(1)，其中k是左子树的节点数，n-k-1是右子树的节点数。把这个式子展开后，整体时间复杂度就是O(n)，因为每个节点只会被递归函数处理一次。

伪代码示例 #

给你写个简单的伪代码，直观看看怎么实现：

def is_binary_search_tree(root):
    def divide_and_conquer(node):
        # 空树视为合法BST，用无穷大/小占位min和max
        if not node:
            return (True, float('inf'), float('-inf'))
        
        # 递归处理左右子树
        left_valid, left_min, left_max = divide_and_conquer(node.left)
        right_valid, right_min, right_max = divide_and_conquer(node.right)
        
        # 合并判断当前子树是否合法
        current_valid = left_valid and right_valid
        if node.left:
            current_valid = current_valid and (left_max < node.val)
        if node.right:
            current_valid = current_valid and (node.val < right_min)
        
        # 计算当前子树的min和max
        current_min = min(left_min, node.val)
        current_max = max(right_max, node.val)
        
        return (current_valid, current_min, current_max)
    
    return divide_and_conquer(root)[0]

关键总结 #

• 分治法的核心是让递归函数返回额外信息（子树的min和max），避免合并时重复遍历子树
• 每个节点的合并操作都是O(1)，整体算法时间复杂度为O(n)，完全符合高效要求

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