问题描述
我想检查单词是否存在于BST中。
有一个错误总是使我false ：
if(listOfWords.contain(word))
write.print(word+" ");
// using this method but it does not work
private boolean contain(englishWord list, String word) {
if (list != null) {
contain(list.getLeft(), word);
if (word.equals(list.getWord())) {
return true;
}
contain(list.getRight(), word);
}
return false;
}
1楼
您的return true语句将递归丢失。
您可以使用类似
if (list != null) {
if (word.equals(list.getWord()) || contain(list.getLeft(), word) || contain(list.getRight(), word)) {
return true;
}
}
return false;
但这将花费O(n)时间复杂度。
BST旨在提供比这更好的性能。
如果您的BST按原样安排，则类似的事情应该起作用（并且比您的算法更有效）。
if (list != null) {
int compare = word.compareTo(list.getWord());
if (compare == 0) {
return true;
} else if (compare > 0) {
return contain(list.getRight(), word);
} else {
return contain(list.getLeft(), word);
}
}
return false;