Validate Binary Search Tree

题目：

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node's key.

The right subtree of a node contains only nodes with keys greater than the node's key.

Both the left and right subtrees must also be binary search trees.

A single node tree is a BST

分析：

解法1的方法是，先DFS到最左下角的点，然后从这个点开始，check下一个点是不是比这个点大。充分利用了BST一进一出这个特点，进去之前什么也不做，一直进去到底，然后改变一个bool，记录这个状态，然后从出的时候开始比较。

其实依然是一个中序遍历的过程

！！！希望引起注意的是解法2，解法2的思路还可以，但实际上是错的，因为有个特殊情况，如果有结点等于INT_MAX或者INT_MIN的时候，这个题目实现不了。你用<=，则在其他的节点违反了定义，你用<则有可能在左下或者右下出bug。

解法：

class Solution {
public:
    /**
     * @param root: The root of binary tree.
     * @return: True if the binary tree is BST, or false
     */
    bool ifReachBottomLeftNode = false;
    int prev = INT_MIN;

    bool isValidBST(TreeNode *root) {
        // write your code here
        if (root == NULL) {
            return true;
        }

        // dfs to the left
        if (!isValidBST(root->left) ) {
            return false;
        }

        // do something here
        if (ifReachBottomLeftNode == true && prev >= root->val) {
            return false;
        }

        ifReachBottomLeftNode = true;
        prev = root->val;

        //dfs to the right
        if (!isValidBST(root->right) ) {
            return false;
        }

        return true;
    }
};

解法2：

class Solution {
public:
    /**
     * @param root: The root of binary tree.
     * @return: True if the binary tree is BST, or false
     */
    bool dfsIsValidBST(TreeNode* root, int left, int right) {
        if (root == NULL) {
            return true;
        }

        return left < root->val
                && right > root->val
                && dfsIsValidBST(root->left, left, root->val)
                && dfsIsValidBST(root->right, root->val, right);
    } 

    bool isValidBST(TreeNode *root) {
        // write your code here
        if (root == NULL) {
            return true;
        }

        return dfsIsValidBST(root, INT_MIN, INT_MAX);
    }
};