98. 验证二叉搜索树

题目

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

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

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

示例 1：

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

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

提示：

树中节点数目范围在[1, 104] 内
-231 <= Node.val <= 231 - 1

代码

/**
 * 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 {
public:
    bool isValidBST(TreeNode* root) {
        long long pre_val=LONG_MIN;//声明一个最小值
        return help(root,pre_val);递归
    }

    bool help(TreeNode* root,long long &pre_val)
    {
        if(!root) return true;//若头结点为空则返回true为二叉搜索树,同时是一个跳出条件
        if(!help(root->left,pre_val))return false;//在递归遍历左子树
        if(root->val<=pre_val)return false;//若根节点的值小于左子树的值则不符合二叉搜索树
        pre_val=root->val;//然后更新值为根节点的值
        if(!help(root->right,pre_val))return false;//然后递归遍历右子树
        return true;//若以上都没有以false返回，则该二叉树为二叉搜索树
    }
};

原理图

方法及解释

提示：算法流程及解释在代码中已标注
方法1:
首先通过中序遍历遍历所有节点，并保存到一次新的数组中，对于二叉搜索树该数组中的元素是升序的，通过设定两个指针，pre与cur比较两者要满足pre小于cur，然后分别往后移动直到遍历完毕，但是该种方法需要一个单独的数组用来保存。

方法2：推荐
仅使用一个pre_val来保存遍历时的前一个节点的值用来和当前节点的值进行比较，此方法也能够实现在遍历二叉树时同时做了比较，空间复杂度为O(1)。

小结

验证二叉搜索树算法主要涉及检查二叉树是否符合二叉搜索树的定义，即对于每个节点，左子树中的所有节点值小于该节点的值，右子树中的所有节点值大于该节点的值。以下是验证二叉搜索树算法的小结：

1. 递归法：可以使用递归方法来验证二叉搜索树。对于每个节点，检查其值是否在给定的范围内，并递归地对左子树和右子树进行验证。

2. 中序遍历法：通过中序遍历二叉搜索树，可以得到一个递增的序列。因此，可以在中序遍历的过程中检查节点值是否递增来验证是否为二叉搜索树。

3. 设定上下限法：在遍历二叉树的过程中，维护一个上下限的范围，对于每个节点，检查其值是否在该范围内，左子树的上限为当前节点值，右子树的下限为当前节点值，然后递归验证左右子树。

4. 使用堆栈或队列：可以使用堆栈或队列来进行迭代遍历二叉树，并在遍历过程中验证每个节点的值是否符合二叉搜索树的定义。

总的来说，验证二叉搜索树算法广泛应用于树的数据结构中，通过合适的方法可以高效地验证给定的二叉树是否符合二叉搜索树的定义。验证二叉搜索树算法主要涉及检查二叉树是否符合二叉搜索树的定义，即对于每个节点，左子树中的所有节点值小于该节点的值，右子树中的所有节点值大于该节点的值。以下是验证二叉搜索树算法的小结：

1. 递归法：可以使用递归方法来验证二叉搜索树。对于每个节点，检查其值是否在给定的范围内，并递归地对左子树和右子树进行验证。

2. 中序遍历法：通过中序遍历二叉搜索树，可以得到一个递增的序列。因此，可以在中序遍历的过程中检查节点值是否递增来验证是否为二叉搜索树。

3. 设定上下限法：在遍历二叉树的过程中，维护一个上下限的范围，对于每个节点，检查其值是否在该范围内，左子树的上限为当前节点值，右子树的下限为当前节点值，然后递归验证左右子树。

总的来说，验证二叉搜索树算法广泛应用于树的数据结构中，通过合适的方法可以高效地验证给定的二叉树是否符合二叉搜索树的定义。

原理图借鉴哔站华南溜达虎，如有侵权联系删除。