为什么当我试图在BST中找到最接近-1的值时，我得到了错误的答案？
为什么当我试图在BST中找到最接近-1的值时，我得到了错误的答案？
提问于 2019-09-30 09:53:22
我目前正在练习我的数据结构技能，我遇到了一个问题。在这个特定的BST中，只要目标是-1，我的代码就不会返回正确的值。它应该返回BST中在值上最接近请求目标的值。
import java.lang.Math;
class Program {
public static int findClosestValueInBst(BST tree, int target) {
int temp = tree.value;
if(temp == target) {
return temp;
}
while(tree.left != null || tree.right != null){
if(tree.value < target){
tree = tree.right;
}
else if(tree.value > target){
tree = tree.left;
}
if(Math.abs(target - tree.value) < Math.abs(target - temp)){
temp = tree.value;
}
}
return temp;
}
static class BST {
public int value;
public BST left;
public BST right;
public BST(int value) {
this.value = value;
}
}
}希望这里的人能知道哪里出了问题。
我在下面贴出了BST组成的值的图片。
回答 1
Stack Overflow用户
发布于 2019-09-30 09:59:32
你有(至少)四个问题：
- 您在更新
temp之前更新tree(如果您在知道tree.value是否是null之前尝试访问它，可能会导致NPE )。 - 您在此过程中不会检查是否完全匹配(可能导致无限循环)。
- 如果您最终遍历到
null元素，则您没有正确处理它(可能导致NPE)。 - 您的d13检查将阻止您访问树的任何叶节点，因为所有叶节点都将d14作为其右/左节点。
在你的while循环中试试这个：
while(tree != null) {
if(Math.abs(target - tree.value) < Math.abs(target - temp)) {
temp = tree.value;
}
if(tree.value < target) {
tree = tree.right;
}
else if(tree.value > target) {
tree = tree.left;
}
else {
return target;
}
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/58160639
复制相关文章
相似问题
腾讯云开发者
