LeetCode hot 100—验证二叉搜索树

题目

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

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

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

示例

示例 1：

输入：root = [2,1,3]
输出：true

示例 2：

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

分析

二叉搜索树具有以下特性：对于树中的每个节点，其左子树中的所有节点值都小于该节点的值，而其右子树中的所有节点值都大于该节点的值，并且左子树和右子树本身也必须是有效的二叉搜索树。

递归法

可以采用递归的方法来遍历整棵二叉树，在遍历过程中，为每个节点设置一个合理的取值范围，通过检查每个节点的值是否在这个范围内，以及递归地检查其左右子树是否也满足二叉搜索树的条件，从而判断整棵树是否为有效的二叉搜索树。

时间复杂度：O()，  是二叉树中的节点数

空间复杂度：O()， 是二叉树的高度

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return isValidBSTHelper(root, LONG_MIN, LONG_MAX);
    }
private:
    bool isValidBSTHelper(TreeNode* node, long minVal, long maxVal) {
        if (node == nullptr) {
            return true;
        }
        // 检查当前节点的值是否在合法范围内
        if (node->val <= minVal || node->val >= maxVal) {
            return false;
        }
        // 递归检查左子树和右子树
        return isValidBSTHelper(node->left, minVal, node->val) &&
               isValidBSTHelper(node->right, node->val, maxVal);
    }
};    

中序遍历法

对二叉搜索树进行中序遍历，得到的节点值序列是一个严格递增的序列。因此，我们可以通过中序遍历二叉树，并在遍历过程中检查节点值是否始终保持递增来判断该二叉树是否为有效的 BST。

时间复杂度：O()，  是二叉树中的节点数

空间复杂度：O()， 是二叉树的高度

class Solution {
private:
    long long prev = LLONG_MIN;  // 记录前一个节点的值，初始化为极小值
public:
    bool isValidBST(TreeNode* root) {
        if (root == nullptr) {
            return true;
        }
        // 递归遍历左子树
        if (!isValidBST(root->left)) {
            return false;
        }
        // 检查当前节点值是否大于前一个节点值
        if (root->val <= prev) {
            return false;
        }
        prev = root->val;  // 更新前一个节点值
        // 递归遍历右子树
        return isValidBST(root->right);
    }
};