98. 验证二叉搜索树

Posted on Edited on In Views: Word count in article: 540 Reading time ≈ 1 mins.

98. 验证二叉搜索树

题目链接：98. 验证二叉搜索树

题目描述

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

  • 节点的左子树只包含 小于 当前节点的数。
  • 节点的右子树只包含 大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

核心思考：中序遍历的单调性

二叉搜索树（BST）的一个核心性质是：其中序遍历（Left -> Root -> Right）得到的结果序列一定是严格单调递增的。

基于这一性质，我们可以将验证过程简化为：

  1. 中序遍历提取序列：使用递归（DFS）对二叉树进行中序遍历，并将遍历到的节点值按顺序存入数组 mid。
  2. 验证单调性：遍历得到的结果数组 mid。如果数组中的任意一个相邻对不满足 mid[i] > mid[i-1]（即出现了相等或递减的情况），则说明该树不是有效的二叉搜索树。

虽然这种方法需要 $O(N)$ 的额外空间来存储中序遍历序列，但其逻辑非常直观且易于实现。

解题思路 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        # 可以不可理解成中序遍历是单调的？
        if not root:
            return
        mid = []
        def dfs(node):
            if node is None:
                return
            dfs(node.left)
            mid.append(node.val)
            dfs(node.right)

        dfs(root)
        if len(mid) == 1:
            return True
        for i in range(1,len(mid)):
            if mid[i] <= mid[i-1]:
                return False
        return True

复杂度分析

  • 时间复杂度：$O(N)$，其中 $N$ 是二叉树的节点数。我们需要遍历每一个节点一次来生成中序遍历序列。
  • 空间复杂度：$O(N)$，我们需要一个额外的数组来存储所有节点的值。此外，递归调用的栈空间在最坏情况下（树呈链状）也是 $O(N)$。