2022 年第 41 题

题目描述

已知一棵二叉树采用数组表示的静态二叉链表存储。请设计一个算法判断该二叉树是否为二叉搜索树。

二叉搜索树要求：

• 左子树上所有关键字都小于根结点关键字。
• 右子树上所有关键字都大于根结点关键字。
• 左右子树本身也都是二叉搜索树。

解题思路

最稳妥的方法是递归维护一个允许区间 (low, high)：

• 当前结点值必须满足 low < val < high。
• 递归左子树时，把上界缩成当前结点值。
• 递归右子树时，把下界提升为当前结点值。

这种写法比“只比较父子大小”更可靠，因为 BST 约束是对子树整体成立的。

手算示例

        8
      /   \
     4     10
    / \      \
   2   6      12

检查过程：

8 在 (-inf, +inf) 内，合法
4 在 (-inf, 8) 内，合法
10 在 (8, +inf) 内，合法
2 在 (-inf, 4) 内，合法
6 在 (4, 8) 内，合法
12 在 (10, +inf) 内，合法

所以是 BST

Python 实现

def is_bst_array(tree, root=0):
    """
    tree 按完全二叉树下标存放，空结点记为 None
    左孩子: 2*i+1，右孩子: 2*i+2
    """
    def dfs(index, low, high):
        if index >= len(tree) or tree[index] is None:
            return True

        val = tree[index]
        if not (low < val < high):
            return False

        return dfs(2 * index + 1, low, val) and dfs(2 * index + 2, val, high)

    return dfs(root, float("-inf"), float("inf"))

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(h)，递归栈深度

易错点

• BST 判断不是只比较父子结点。
• 若数组中有空洞，要先判断下标是否合法以及结点是否为空。
• 默认按严格 BST 处理，不允许重复元素落在左右子树边界上。

对应题

来源	题目	相似度	主要差异
LeetCode	98. 验证二叉搜索树	90%	真题多用静态数组存储
PAT 甲级	1043 Is It a Binary Search Tree	90%	存储形式不同

难度

⭐️⭐️