此函数中的"min"和"max"是什么来检查二叉树是否是有效的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

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

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