java - 当我尝试在BST中找到最接近-1的值时，为什么会得到错误的答案？

我目前正在练习我的数据结构技能，遇到了一个问题。在此特定的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组成的值的图片下面发布了图片。

BST Values

最佳答案

您（至少）有四个问题：


您在更新tree之前先更新temp（如果尝试在不知道tree.value之前访问null，可能会导致NPE）。
您一路上不检查是否完全匹配（可能导致无限循环）。
如果最终遍历到null元素，则说明处理不正确（可能导致NPE）。
您的tree.left != null || tree.right != null检查将阻止您访问树的任何叶节点，因为所有叶节点的右/左节点均为null。


在您的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;
    }
}

关于java - 当我尝试在BST中找到最接近-1的值时，为什么会得到错误的答案？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/58160639/