java - 了解 Java 递归代码以检查树是否是有效的二叉搜索树

Question

我正在研究 Java 中的数据结构(目前是树)。我有一个函数可以确定一棵树是否是有效的 BST。该函数运行正常，但我无法理解它是如何运行的。该功能如下:

//call from Main method 
boolean isBST = theTree.isValidBST(theTree.root);
System.out.println("isBST??" +isBST);

//actual method body
public boolean isValidBST(Node root) {
    return isValidBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);    
}

public boolean isValidBST(Node focusNode, int min, int max){
    if(focusNode==null) 
        return true;
     System.out.println("Comparing "+focusNode.key+ " with "+min+" min value ");
     System.out.println("Comparing "+focusNode.key+ " with "+max+" max value ");
        if(focusNode.key <= min || focusNode.key >= max)
            return false;

    return isValidBST(focusNode.leftChild, min, focusNode.key) && isValidBST(focusNode.rightChild, focusNode.key, max);
}

我的实际树看起来像这样:

上述函数的输出是:

Comparing 50 with -2147483648 min value 
Comparing 50 with 2147483647 max value 
Comparing 25 with -2147483648 min value 
Comparing 25 with 50 max value 
Comparing 15 with -2147483648 min value 
Comparing 15 with 25 max value 
Comparing 30 with 25 min value 
Comparing 30 with 50 max value 
Comparing 75 with 50 min value 
Comparing 75 with 2147483647 max value 
Comparing 85 with 75 min value 
Comparing 85 with 2147483647 max value 
isBST??true

现在有人能解释一下这里的执行是如何进行的吗？如何对函数进行嵌套(递归)调用？我对递归函数调用缺乏很多理解。如果有人能让我理解这段代码，我将能够解决许多与树相关的递归问题。寻找一些帮助。多谢。

Answer 1

为了使树成为二叉搜索树 (BST)，它必须满足这些条件。

1. 每个节点都必须有一个键或关联值。
2. 每个节点最多只能有两个不同的子树，通常表示为左子树和右子树。
3. 每个节点中的键必须大于左子树中存储的所有键，并且小于右子树中的所有键。

具体来说，该函数正在验证树是否满足第三个条件(假设前两个条件为真)。此递归函数遍历树，直到到达叶节点并确保每个子节点小于其父节点(如果它是左子节点)或大于其父节点(如果它是右子节点)。有两个基本情况条件(如果您不知道什么是基本情况，您需要阅读有关递归的更多内容)。

1. 函数已在叶节点处终止(该节点为空)。
2. 该函数使上述条件无效。

树遍历发生在这一行:

return isValidBST(focusNode.leftChild, min, focusNode.key) && isValidBST(focusNode.rightChild, focusNode.key, max);

每个节点必须先验证其左右子树，然后节点本身才能被视为有效。