/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

class Solution {

public:

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {

        if (root==NULL)

            return 0;

        if(p->val<root->val&&q->val<root->val)

            return lowestCommonAncestor(root->left,p,q);

        if(p->val>root->val&&q->val>root->val)

            return lowestCommonAncestor(root->right,p,q);

        return root;

    }

};

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

class Solution {

public:

    bool isValidBST(TreeNode* root) {

        return isValidBST(root,LONG_MIN,LONG_MAX);

    }

    bool isValidBST(TreeNode *root,long mn,long mx){

        if(!root) return true;

        if(root->val<=mn||root->val>=mx) return false;

        return isValidBST(root->left,mn,root->val)&&isValidBST(root->right,root->val,mx);

    }

};

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

class Solution {

public:

    bool isPre = false;

    int pre = -1;

    bool isValidBST(TreeNode* root) {

        return inOrder(root);

    }

    bool inOrder(TreeNode* node){

        if(node == NULL)

            return true;

        if(!inOrder(node->left))

            return false;

        if(isPre && pre >= node->val)

            return false;

        isPre = true;

        pre = node->val;

        if(!inOrder(node->right))

            return false;

        return true;

    }

};