学步园

给定一棵二叉树的根结点，树中每个结点包含一个整数值val以及左右儿子结点指针left, right，判断该树是否为二叉搜索数(Binary
Search Tree)。

二叉搜索树的简单定义：对于树中任意一棵以T为根结点的子树，T的val值大于等于其左子树中任意结点的val值，小于其右子树中任意结点的val值。

跟Leetcode上那个还有点不一样。

这里是要求左子树全部小于等于当前值，右子树必须全部大于。所以用pre来中序遍历不好区分当前是否可以等。

这里用另一种范围限定的方法来做。

/*
树结点的定义(请不要在代码中定义该结构)
struct TreeNode {
  int val;
  TreeNode *left, *right;
}*/
const int INT_MIN =-10000000;
const int INT_MAX = 10000000;
bool _preorder(TreeNode* root,int min,int max);
bool isBST(TreeNode *root) {
	if ( !root ) 
		return true;
	int pre=INT_MIN;
	int canEqual=1;
	return _preorder(root,INT_MIN,INT_MAX);	
}
bool _preorder(TreeNode* root,int min,int max)
{
	if (!root)
		return true;
	if (root->val<min||root->val>max)
		return false;
	if ( !_preorder(root->left,min,root->val) )
		return false;
	return _preorder(root->right,root->val+1,max);
}