当我试图在BST中找到最接近-1的值时，我得到了错误的答案？

Question

我目前正在练习我的数据结构技能，遇到了一个问题。在此特定的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

Answer 1

您（至少）有四个问题：

1. 您在更新tree之前先更新temp（如果您在不知道tree.value之前尝试访问null，可能会导致NPE。
2. 您在执行过程中不会检查是否完全匹配（可能会导致无限循环）。
3. 如果最终遍历到null元素，则处理不正确（可能会导致NPE）。
4. 您的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;
    }
}