java检查二叉树是否为有效BST的函数中的“min”和“max”是什么？

Question

下面的代码来自Finding if a Binary Tree is a Binary Search Tree

bool IsValidBST(BinaryNode node, int MIN, int MAX) 
{
     if(node == null)
     return true;

    if(node.element > MIN 
         && node.element < MAX
         && IsValidBST(node.left,MIN,node.element)
         && IsValidBST(node.right,node.element,MAX))
         return true;
     else 
         return false;
}

这里如何使用MIN和MAX？它们代表什么价值观？为什么它们需要通过函数传递

Answer 1

它们必须通过函数来传递，以便递归地调用它，并增加缩小范围，就像这里一样

当然，对于第一个调用，您可以从树中确定最小值和最大值，但对于后续调用，您必须这样传递

Answer 2

您应该如下调用函数。其中INT_MIN和INT_MAX是常数定义的

IsValidBST (root, INT_MIN, INT_MAX)

但这种方法并不适用于所有数据。意思是，我们不知道最小值和最大值的数据，比如字符串或任意用户定义的类型

要确定给定的BT是否是任何数据类型的BST，需要使用以下方法。 1.使用顺序遍历调用递归函数，直到叶节点结束 2.自己建立自己的最小值和最大值

前提是，树元素必须定义小于/大于运算符

#define MIN (FirstVal, SecondVal) ((FirstVal) < (SecondVal)) ? (FirstVal):(SecondVal)
#define MAX (FirstVal, SecondVal) ((FirstVal) > (SecondVal)) ? (FirstVal):(SecondVal)

template <class T>
bool IsValidBST (treeNode &root)
{

   T min,  max;
   return IsValidBST (root, &min, &max);
}

template <class T>
bool IsValidBST (treeNode *root, T *MIN , T *MAX)
{
   T leftMin, leftMax, rightMin, rightMax;
   bool isValidBST;

   if (root->leftNode == NULL && root->rightNode == NULL)
   {
      *MIN = root->element;
      *MAX = root->element;
      return true;
   }

  isValidBST = IsValidBST (root->leftNode, &leftMin, &leftMax);

  if (isValidBST)
    isValidBST = IsValidBST (root->rightNode, &rightMin, &rightMax);

  if (isValidBST)
  {
     *MIN = MIN (leftMIN, rightMIN);
     *Max = MAX (rightMax, leftMax);
  }

  return isValidBST;
}