//中序遍历

class Solution {

public:

    TreeNode* pre;

    bool isValidBST(TreeNode* root) {

        if(!root) return true;

        stack<TreeNode*>ss;

        TreeNode* cur=root;

        while(ss.size()||cur)

        {

            while (cur)

            {

                ss.push(cur);

                cur=cur->left;

            }

            cur=ss.top();

            ss.pop();

            if(pre&&pre->val >= cur->val) return false;

            pre=cur;

            cur=cur->right;

        }

        return true;

    }

};

//递归我是真的想不开啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊

//啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊

//啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊

//啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊

class Solution{

private:

     bool anotherBST(TreeNode* root,int* lower,int* upper)

     {

          if(root==NULL) return true;

          if(lower!=NULL&&root->val<=(*lower)) return false;

          if(upper!=NULL&&root->val>=(*upper)) return false;

          if(!anotherBST(root->left,lower,&(root->val))) return false;

          if(!anotherBST(root->right,&(root->val),upper)) return false;

          return true;

     }

public:

     bool isValidBST(TreeNode* root)

          {

               return anotherBST(root,NULL,NULL);

          }

};