尝试运行递归算法来找出某棵树是否是 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;
}
我不确定我的算法有什么问题。有什么帮助吗?
最佳答案
问题是您的实现忽略了方法递归调用的返回值:
checkBST(root.left);
...
checkBST(root.right);
无论返回值如何,您的代码都会继续运行。相反,它应该检查返回值,如果子树的检查返回 false
,则返回 false
:
if (!checkBST(root.left)) {
return false;
}
...
if (!checkBST(root.right)) {
return false;
}
关于java - 无法检测这是否是 BST,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43835999/