[leetcode]Validate Binary Search Tree 验证二叉搜索树

此题很容易犯一个错误：

将current结点的值和左右孩子比较，如果满足要求(即current结点的值大于左孩子，小于右孩子)，就递归调用函数验证左右孩子为根结点的子树。

这样的验证方式是不对的，因为二叉搜索树的要求是：current 结点值大于左子树所有结点值，小于右子树所有结点值。上面的验证方式只能保证左右子树的根结点满足这种要求。

思路一：利用中序遍历来判断

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        vector<int>res;
        In_OrderTree(root,res);
        for(int i=1;i<res.size();i++){
            if(res[i]<=res[i-1])return false;
        }
        return true;
    }
    void In_OrderTree(TreeNode* root,vector<int>&res){
        if(!root)return;
        In_OrderTree(root->left,res);
        res.push_back(root->val);
        In_OrderTree(root->right,res);
    }
};

思路二：利用二插搜索树性质

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return help(root,LONG_MIN, LONG_MAX);
        
    }
    
    bool help(TreeNode* root,long mn, long mx)
    {
        if(!root)return true;
        if(root->val<=mn||root->val>=mx)return false;
        return help(root->left,mn,root->val)&&help(root->right,root->val,mx);
        
    }
};