18 | 面试题：验证二叉搜索树-算法面试通关 50 讲

当前位置:　首页>> 技术小册>> 算法面试通关 50 讲

### 18 | 面试题：验证二叉搜索树

在算法面试中，验证二叉搜索树（Binary Search Tree, BST）是一个既经典又富有挑战性的题目。二叉搜索树是一种特殊的二叉树，其中每个节点都遵循以下性质：节点的左子树只包含小于节点值的元素，节点的右子树只包含大于节点值的元素，且左右子树也必须是二叉搜索树。本题要求设计一个算法来验证给定的二叉树是否满足二叉搜索树的定义。

#### 一、问题解析

首先，我们需要明确二叉搜索树的定义，并据此设计出验证算法。直观上，我们可以遍历整棵树，并检查每个节点的值是否满足二叉搜索树的性质。然而，简单的遍历方法（如先序、中序、后序遍历）虽然能访问到所有节点，但直接利用它们来验证二叉搜索树性质并不高效。特别是，中序遍历（左-根-右）能够产生一个递增的元素序列，这是验证二叉搜索树最直观且有效的方法。

#### 二、解题思路

1. **递归中序遍历验证**：
   - 使用递归进行中序遍历，同时跟踪当前遍历到的最小值（初始化为负无穷大或树的最小值以下的一个值）。
   - 遍历过程中，检查当前节点的值是否大于前一个遍历到的节点的值。
   - 如果发现不满足条件的节点，立即返回false，表示这不是一棵二叉搜索树。
   - 如果遍历完成没有发现问题，则返回true。

2. **非递归中序遍历验证**：
   - 使用栈来模拟递归过程，同样进行中序遍历。
   - 维护一个指向当前遍历到的最小值的指针或变量。
   - 在遍历过程中，不断比较并更新最小值，检查是否有违反二叉搜索树性质的情况。

3. **利用BST性质直接判断**：
   - 另一种思路是直接利用二叉搜索树的性质，对每个节点，检查其左子树中的所有节点值是否都小于该节点值，右子树中的所有节点值是否都大于该节点值。
   - 这通常需要通过递归或迭代方式，对左右子树分别进行类似的检查。

#### 三、递归中序遍历验证实现

以下是使用递归中序遍历验证二叉搜索树的Python代码示例：

```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def isValidBST(root, prev=float('-inf')):
    # 空树是BST
    if not root:
        return True
    
    # 检查左子树
    if not isValidBST(root.left, prev):
        return False
    
    # 检查当前节点
    if root.val <= prev:
        return False
    
    # 更新prev为当前节点值，继续检查右子树
    return isValidBST(root.right, root.val)

# 调用函数验证
# 假设已有一棵二叉树root
# result = isValidBST(root)
# print(result)
```

#### 四、非递归中序遍历验证实现

接下来是非递归版本的实现，使用栈来模拟递归过程：

```python
def isValidBSTIterative(root):
    stack, prev = [], float('-inf')
    current = root
    
    while stack or current:
        while current:
            stack.append(current)
            current = current.left
        
        current = stack.pop()
        
        if current.val <= prev:
            return False
        
        prev = current.val
        current = current.right
    
    return True

# 调用函数验证
# result = isValidBSTIterative(root)
# print(result)
```

#### 五、性能分析

- **时间复杂度**：对于递归和非递归的中序遍历验证方法，时间复杂度均为O(n)，其中n是树中节点的数量，因为我们需要遍历树中的每个节点一次。
- **空间复杂度**：递归方法的空间复杂度取决于树的高度，最坏情况下（树退化为链表）为O(n)，最好情况下（树完全平衡）为O(log n)。非递归方法使用栈来模拟递归过程，空间复杂度同样为O(n)（最坏情况），但在大多数情况下会优于递归方法，因为它避免了递归调用栈的开销。

#### 六、扩展思考

- **变种问题**：有些面试题会要求验证一个二叉树是否是平衡二叉搜索树（Balanced Binary Search Tree），即在满足二叉搜索树性质的同时，树的任意两个叶子节点的最大深度差不超过1。这通常需要额外的深度检查。
- **优化策略**：在实际应用中，如果频繁需要进行二叉搜索树的验证，可以考虑在树的结构中维护额外的信息（如节点值范围、子树高度等），以加快验证过程。

通过以上分析，我们不仅掌握了验证二叉搜索树的基本方法，还理解了其背后的算法思想和性能考量，这对于准备算法面试或解决类似问题具有重要意义。

该分类下的相关小册推荐：

数据结构与算法之美

业务开发实用算法精讲

编程之道-算法面试(上)

数据结构与算法(下)

数据结构与算法(中)

数据结构与算法(上)

编程之道-算法面试(下)