【力扣刷题实战】验证二叉搜索树

大家好，我是小卡皮巴拉

文章目录

目录

力扣题目：验证二叉搜索树

题目描述

解题思路

问题理解

算法选择

具体思路

解题要点

完整代码（C++）

兄弟们共勉 ！！！ 

每篇前言

博客主页：小卡皮巴拉

咱的口号：🌹小比特，大梦想🌹

作者请求：由于博主水平有限，难免会有错误和不准之处，我也非常渴望知道这些错误，恳请大佬们批评斧正。

力扣题目：验证二叉搜索树

原题链接：98. 验证二叉搜索树 - 力扣（LeetCode）

题目描述

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

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

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

示例 1：

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

示例 2：

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

解题思路

问题理解

本题给定一个二叉树的根节点，需要判断该二叉树是否是一个有效的二叉搜索树。有效二叉搜索树的定义为：节点的左子树只包含小于当前节点的数；节点的右子树只包含大于当前节点的数；所有左子树和右子树自身也必须是二叉搜索树。

算法选择

采用中序遍历的递归算法。因为二叉搜索树的中序遍历结果是一个递增的有序序列，所以通过中序遍历二叉树，检查每个节点的值是否大于前一个访问节点的值，就可以判断该二叉树是否为有效的二叉搜索树。

具体思路

1. 递归终止条件：检查当前节点 root 是否为空。如果为空，根据定义空树是有效的二叉搜索树，直接返回 true。

2. 递归遍历左子树：递归调用 isValidBST(root->left) 判断当前节点的左子树是否是有效的二叉搜索树，并将结果存储在 left 变量中。如果 left 为 false，说明左子树不是有效的二叉搜索树，整棵树也不是，直接返回 false（剪枝操作）。

3. 检查当前节点：比较当前节点 root 的值与前一个访问节点的值（存储在 prev 中）。如果 root->val > prev，则当前节点满足二叉搜索树的条件，将 cur 设为 true；否则，cur 设为 false。如果 cur 为 false，说明当前节点不满足条件，整棵树不是有效的二叉搜索树，直接返回 false（剪枝操作）。更新 prev 的值为当前节点 root 的值。

4. 递归遍历右子树：递归调用 isValidBST(root->right) 判断当前节点的右子树是否是有效的二叉搜索树，并将结果存储在 right 变量中。如果 right 为 false，说明右子树不是有效的二叉搜索树，整棵树也不是，直接返回 false（剪枝操作）。

5. 返回结果：只有当左子树、右子树都有效且当前节点也满足条件时（即 left、right 和 cur 都为 true），整棵树才是有效的二叉搜索树，返回 true；否则返回 false。

解题要点

1. 中序遍历的应用：理解二叉搜索树的中序遍历结果是递增序列这一特性，通过中序遍历递归地检查每个节点的值是否符合要求。

2. 剪枝操作：在递归过程中，一旦发现左子树、当前节点或右子树不满足条件，立即返回 false，避免不必要的后续计算，提高算法效率。

3. 变量的使用：正确使用 prev 变量记录前一个访问节点的值，以及 left、right 和 cur 变量来记录各个部分的有效性判断结果。

完整代码（C++）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    // 用于记录前一个访问节点的值，初始化为 long 类型的最小值
    long prev = LONG_MIN;
public:
    bool isValidBST(TreeNode* root) 
    {
        // 如果当前节点为空，根据定义空树是有效的二叉搜索树，返回 true
        if(root == nullptr) return true;

        // 递归地判断当前节点的左子树是否是有效的二叉搜索树
        bool left = isValidBST(root->left);
        // 剪枝：如果左子树不是有效的二叉搜索树，整棵树也不是，直接返回 false
        if(left == false) return false;
        
        // 用于记录当前节点是否满足二叉搜索树的条件（当前节点值大于前一个访问节点的值）
        bool cur = false;
        // 判断当前节点的值是否大于前一个访问节点的值
        if(root->val > prev)
            cur = true;
        // 剪枝：如果当前节点不满足条件，整棵树不是有效的二叉搜索树，直接返回 false
        if(cur == false) return false;
        // 更新前一个访问节点的值为当前节点的值
        prev = root->val;

        // 递归地判断当前节点的右子树是否是有效的二叉搜索树
        bool right = isValidBST(root->right);
        // 剪枝：如果右子树不是有效的二叉搜索树，整棵树也不是，直接返回 false
        if(right == false) return false;
        // 只有当左子树、右子树都有效且当前节点也满足条件时，整棵树才是有效的二叉搜索树
        return left && right && cur;
    }
};

兄弟们共勉 ！！！ 

码字不易，求个三连

抱拳了兄弟们！