98. Validate Binary Search Tree两

判断是否为二叉查找树的题，先给一种方法，可是过不去某个case

/**
 * 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:
//这种方法当test case为[-2147483648,null,2147483647]或[-2147483648］或[2147483647]时无法通过
    bool isValidBST(TreeNode* root) 
        return helper(root, INT_MIN, INT_MAX);
        
    }
    bool helper(TreeNode* root, int min, int max){
        if(root == NULL) return true;
        
        if(root->val <= min || root->val >= max)
            return false;
        return helper(root->left, min, root->val) && helper(root->right, root->val, max);
        
    }
};

换另外一种方法（In-order tranversal）:

/**
 * 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) 
    {
        TreeNode* pre = NULL;
        return helper(root, pre);
        
    }
    bool helper(TreeNode* root, TreeNode* &pre){
        if(root == NULL) return true;
        if(!helper(root->left, pre)) return false;
        if(pre != NULL && pre->val >= root->val)
                return false;
        pre = root;
        return helper(root->right, pre);
        
    }
};

这题值得好好回味一下