leetcode 98.验证二叉搜索树

二叉搜索树的特点就是左子树的值都小于根结点，右子树的值都大于根结点。那么我们就可以进行判断操作了。
方法一：递归方法，从头结点开始，均需要每个结点的值在一个范围内。这个范围的确定会随着向下的遍历，慢慢缩小。
方法二：迭代的方法
采用中序遍历的方法，如果出现上一个访问的结点比当前的结点的值小，那么此二叉树不是二叉搜索树。

class Solution {
public:
//方法一
    // //判断是否是二叉搜索树
    // //递归实现方法
    bool isValidBST(TreeNode* root) 
    {
        return check(root,LONG_MIN,LONG_MAX); 
    }

    //传入参数值说明
    bool check(TreeNode* root,int leftval,int rightval)
    {   //如果根节点为空格，返回true
        if(root == nullptr)
        {
            return true;
        }
        //如果根节点的值不在最大最小值中间，返回错误
        if(root->val >= rightval || root->val <= leftval)
        {
            return false;
        }
        //如果根节点的值在最大最小值之间

        return check(root->left,leftval,root->val) && check(root->right,root->val,rightval);
    }

    //方法二
    //非递归实现中序遍历
    bool isValidBST(TreeNode* root) 
    {
        int val = LONG_MIN;
        if(root == nullptr)
        {
            return true;
        }
        //创建一个栈来保存访问的结点
        stack  stk;
        TreeNode * node = root;
        //当栈不为空或者结点指针不为空
        while(stk.empty() == false  || node != nullptr)
        {
            while(node)
            {
                stk.push(node);     //node结点地址压入栈中
                node = node->left;
            }
            node = stk.top();       //node获取上个结点
            stk.pop();              //弹出栈顶结点
            if(node->val <= val)
            {
                return false;
            }
            
            val = node->val;
            node = node->right;     //访问右结点
        }
        return true;

    }
};