98.验证二叉搜索树

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

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

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

示例 1：

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

思路：二叉搜索树中序遍历可以升序输出结点值。判断中序遍历的结点是不是比上一个中序遍历过的结点的值更大。 

class Solution {
public:
    long maxVal=LONG_MIN;// 因为后台测试数据中有int最小值
    bool isValidBST(TreeNode* root) 
    {
        if (root == NULL) return true;
        bool left = isValidBST(root->left);
        if (maxVal < root->val) 
        maxVal = root->val;
        else 
        return false;//有重复元素，maxVal>=root->val都不算二叉搜索树
        bool right = isValidBST(root->right);
        return left&&right;
    }
};

if(cur!=nullptr&&cur->val>=root->val)中 cur!=nullptr解决了刚进入递归时cur==nullptr的情况，很巧妙！

class Solution {
public:
    TreeNode* cur;
    bool isValidBST(TreeNode* root) 
    {
        if (root == NULL) return true;
        bool left = isValidBST(root->left);
        if(cur!=nullptr&&cur->val>=root->val) return false;
        cur=root;
        bool right = isValidBST(root->right);
        return left&&right;
    }
};