什么是“分钟”？和“最大”在这个函数中检查二叉树是否是有效的 BST？

Question

下面的代码来自 查找二叉树是否是二叉搜索树。

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

[MIN, MAX] 表示当前节点中有效值的范围。对于第一个节点，这将是 INT_MIN 和 INT_MAX，因为它可以具有任意值，但对于其子节点，我们需要检查 BST 属性 - 所有左子节点不应大于当前节点，所有右子节点不应小于当前节点。这就是为什么我们分别更改它们的 MIN 和 MAX 值。

注意：如果在树中可以有重复值，请将检查更改为：

 if(node.element >= MIN 
   && node.element <= MAX
   && IsValidBST(node.left,MIN,node.element)
   && IsValidBST(node.right,node.element,MAX))

否则您将得到无效结果。

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

Answer 3

它们必须通过函数传递，以便以越来越小的范围递归调用，就像这里一样。

当然，对于第一次调用，您可以从树中确定 MIN 和 MAX，但对于后续调用，您必须像这样传递下去。

Answer 4

这里MIN MAX指定树中存储的最小值和树中存储的最大值。

I think simplest way to check the valid BST tree is traverse inorder and check if
the values are in sorted order or not? if all the values are in sorted order that
means its valid BST.

实现
http://justprogrammng.blogspot .com/2012/06/check-if-tree-is-bst-on-code-interview.html