力扣98：验证二叉搜索树

力扣98：验证二叉搜索树

题目描述

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

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

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

输入输出样例

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

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

解法1：使用递归的思想实现

bool isValid(TreeNode *root,long long lower,long long upper)
{
    
    if(root==nullptr)
    {
    
        return true;
    }
    if(root->val<=lower||root->val>=upper)
    {
    
        return false;
    }
    return isValid(root->left,lower,root->val)&&isValid(root->right,root->val,upper);
}


//使用递归的思想进行实现
bool isValidBST(TreeNode* root)
{
    
    return isValid(root,LONG_MIN,LONG_MAX);
} 

解法2：使用中序遍历

中序遍历二叉搜索树得到的也是一个升序的数组

//根据二叉搜索树中序遍历时升序的性质进行实现
bool isValidBST2(TreeNode* root) 
{
    
    if(!root)
    {
    
        return true;
    }
    stack<TreeNode *>stk;
    vector<int>res;

    while(!stk.empty()||root!=nullptr)
    {
    
        while(root!=nullptr)
        {
    
            stk.push(root);
            root=root->left;
        }

        TreeNode *temp;
        temp=stk.top();
        // cout<<temp->val<<" ";
        res.push_back(temp->val);
        stk.pop();
        root=temp->right;
    }

    int length=res.size();
    for(int i=1;i<length;i++)
    {
    
        if(res[i]<=res[i-1])
        {
    
            return false;
        }
    }
    return true;
}