学步园

题目：判断一个棵树是否是BST树

思路：BST树要求当前节点的所有左子树的节点的key小于当前节点的key,右子树节点的key大于当前节点的key。例如

二叉树{10,5,#,#,15,6,20}，其判断过程是这样：

1.到达key=10的节点，min=INT_MIN, max=INT_MAX， min<10<max，继续

2.到达key=5的节点，min=INT_MIN,max=10, min<5<max，继续

3.到达key=15的节点，min=10, max=INT_MAX, min<15<max，继续

4.到达key=6的节点，min=10，max=15, 不满足min<6<max，返回false

由此可见，把当前节点作为最大值传给左子树，作为最小值传给右子树，然后判断

class Solution {
public:
    bool isBSTHelper(TreeNode* root, int low, int high)
    {
        if (root == NULL)
        {
            return true;
        }
        if (root->val > low && root->val <high)
        {
            return isBSTHelper(root->left, low, root->val) && isBSTHelper(root->right, root->val, high);
        }
        else
        {
            return false;
        }
    }
    bool isValidBST(TreeNode *root) {
        return isBSTHelper(root, INT_MIN, INT_MAX);
    }
};