/*判斷左子樹(shù)的結(jié)點(diǎn)值是否都小于val*/
bool isSubTreeLessThan(BinaryTree *p, int val)
{
 if (!p) return true;
 return (p->data < val &&
     isSubTreeLessThan(p->left, val) &&
     isSubTreeLessThan(p->right, val));
}
/*判斷右子樹(shù)的結(jié)點(diǎn)值是否都大于val*/
bool isSubTreeGreaterThan(BinaryTree *p, int val)
{
 if (!p) return true;
 return (p->data > val &&
     isSubTreeGreaterThan(p->left, val) &&
     isSubTreeGreaterThan(p->right, val));
}
/*判定二叉樹(shù)是否是二叉搜索樹(shù)*/
bool isBSTBruteForce(BinaryTree *p)
{
 if (!p) return true;
 return isSubTreeLessThan(p->left, p->data) &&
     isSubTreeGreaterThan(p->right, p->data) &&
     isBSTBruteForce(p->left) &&
     isBSTBruteForce(p->right);
}

int isBST(struct node* node)
{
 if (node==NULL) return(true);
 //如果左子樹(shù)最大值>=當(dāng)前node的值，則返回false
 if (node->left!=NULL && maxValue(node->left) >= node->data)
  return(false);
 // 如果右子樹(shù)最小值<=當(dāng)前node的值，返回false
 if (node->right!=NULL && minValue(node->right) <= node->data)
  return(false);
 // 如果左子樹(shù)或者右子樹(shù)不是BST，返回false
 if (!isBST(node->left) || !isBST(node->right))
  return(false);
 // 通過(guò)所有測(cè)試，返回true
 return(true);
}

int isBST2(struct node* node)
{
   return(isBSTUtil(node, INT_MIN, INT_MAX));
}
/*
給定的二叉樹(shù)是BST則返回true，且它的值 >min 以及 < max.
*/
int isBSTUtil(struct node* node, int min, int max)
{
   if (node==NULL) return(true);
   // 如果不滿足min和max約束，返回false
   if (node->data<=min || node->data>=max) return(false);
   // 遞歸判斷左右子樹(shù)是否滿足min和max約束條件
   return
     isBSTUtil(node->left, min, node->data) &&
     isBSTUtil(node->right, node->data, max)
   );
}

bool isBSTInOrder(BinaryTree *root)
{
 int prev = INT_MIN;
 return isBSTInOrderHelper(root, prev);
}
/*該函數(shù)判斷二叉樹(shù)p是否是一棵二叉搜索樹(shù)，且其結(jié)點(diǎn)值都大于prev*/
bool isBSTInOrderHelper(BinaryTree *p, int& prev)
{
 if (!p) return true;
 if (isBSTInOrderHelper(p->left, prev)) { // 如果左子樹(shù)是二叉搜索樹(shù)，且結(jié)點(diǎn)值都大于prev
  if (p->data > prev) { //判斷當(dāng)前結(jié)點(diǎn)值是否大于prev，因?yàn)榇藭r(shí)prev已經(jīng)設(shè)置為已經(jīng)中序遍歷過(guò)的結(jié)點(diǎn)的最大值。
   prev = p->data;
   return isBSTInOrderHelper(p->right, prev); //若結(jié)點(diǎn)值大于prev，則設(shè)置prev為當(dāng)前結(jié)點(diǎn)值，并判斷右子樹(shù)是否二叉搜索樹(shù)且結(jié)點(diǎn)值都大于prev。
  } else {
   return false;
  }
 }
 else {
  return false;
 }
}