Validate binary search tree

关于这道题目，不得不感慨leetcode真的是一个不错的网站，之前的代码是有bug的，当时AC了，现在测试用例更加完善了，于是不能AC了。

题目描述：

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.

class Solution {
private:
    void traverse(TreeNode *root , vector<int> &in)
    {
        if(root == nullptr) return;
        traverse(root->left,in);
        in.push_back(root->val);
        traverse(root->right,in);
    }

public:
    bool isValidBST(TreeNode *root) {
        if(root == nullptr) return true;
        vector<int> in;
        traverse(root,in);
        for(int i=0;i+1<in.size();++i)
            if(in[i] >= in[i+1]) return false;
        return true;
    }
};

class Solution { //代码不够robust！！！有错误！！
    bool helper(TreeNode *root, int min, int max)
    {
        if(root == nullptr) return true;
        return (root->val > min && root->val < max ) && helper(root->left,min,root->val) && helper(root->right,root->val, max);
    }
    
public:
    bool isValidBST(TreeNode *root) {
        if(root == nullptr) return true;
        int min = INT_MIN, max = INT_MAX;
        return helper(root, min,max);
    }
};

之前是逐渐的减少每个子树的取值范围，检验即可，直到根节点。这个代码对于一般的例子是没有任何问题的，但是对于树中本身就含有INT_MIN和INT_MAX的节点时，上述代码是错误的，列出几个case：

Case 1: 只有一个根节点，根节点的值就是INT_MIN或者INT_MAX.结果输出false，正确答案是TRUE。

于是我想到了对于特殊值的地方允许等号存在。代码极其繁琐，就不贴出来了，但是还是不对，比如下面的Case

Case 2: 根节点的值是INT_MIN ,根节点的右子节点为INT_MAX, 根节点的右子树的左子树节点的值为INT_MIN.

.......

Validate binary search tree

原文：http://blog.csdn.net/xuqingict/article/details/41180339