判断是否二叉搜索树

转自：http://blog.163.com/yichangjun1989@126/blog/static/1319720282014641735487/

 

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

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

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

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

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

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

   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);
}