java - 无法检测这是否是 BST

Question

尝试运行递归算法来找出某棵树是否是 BST(二叉搜索树)。

boolean checkBST(Node root) {
    boolean isBST = true;
    if(root == null){
        return false;
    }
    if(root.left != null){
        if( isLessThan(root.data, root.left.data) == false ) {
            isBST = false;
            return isBST;
        } else
            checkBST(root.left);
    }
    if(root.right != null){
        if(isGreaterThan(root.data, root.right.data) == false) {
            isBST = false;
            return isBST;
        } else
            checkBST(root.right);
    }
    return isBST;
}


boolean isLessThan(int value1, int value2){
    if(value2< value1){
        return true;
    } 
    return false;
}

boolean isGreaterThan(int value1, int value2){
    if(value1 < value2){
        return true;
    } else
        return false;
}

我不确定我的算法有什么问题。有什么帮助吗？

Answer 1

问题是您的实现忽略了方法递归调用的返回值:

checkBST(root.left);
...
checkBST(root.right);

无论返回值如何，您的代码都会继续运行。相反，它应该检查返回值，如果子树的检查返回 false，则返回 false:

if (!checkBST(root.left)) {
    return false;
}
...
if (!checkBST(root.right)) {
    return false;
}