了解 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)，它必须满足这些条件。

每个节点必须有一个键或关联值。
每个节点最多必须有两个可区分的sub-trees，通常表示为左和右。
每个节点中的键必须大于左侧sub-tree中存储的所有键，并且小于右侧sub-tree中的所有键。

具体来说，此函数正在验证树是否满足已经假设前两个条件为真的第三个条件。这个递归函数遍历树，直到它到达一个叶节点，并确保每个 child 节点小于它的 parent（如果它是左 child）或大于它的 parent（如果是右child）。有两个基本情况条件（如果您不知道基本情况是什么，则需要阅读更多有关递归的信息）。

函数在叶节点处终止（该节点为空）。
函数使上述条件无效。

树遍历发生在这一行：

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

在节点本身被认为有效之前，每个节点都必须验证其左右子树。

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

Understanding Java Recursion code to check if tree is a valid Binary Search Tree

java

debugging

tree

recursion

binary-search-tree