为什么在给定目标值的情况下尝试在 BST 中找到最接近的值时得到错误答案？

Question

正确答案和我的答案只有一点不同，那就是我是遍历整棵树，而不是每次递归比较目标和节点值，去掉二分之一的树。请帮我解释一下。谢谢

我的代码：

import java.util.*;

class Program {
     public static int findClosestValueInBst(BST tree, int target) {
         //int closest = Integer.MAX_VALUE;
        // int val = 0;
         int vl = findClosestValueInBst1(tree, target, tree.value);
         return vl;
     }

  public static int findClosestValueInBst1(BST tree, int target, int val) {
    //  System.out.println((closest + "   " + Math.abs(tree.value - target)));
        //c = closest;
        if(( Math.abs(target - tree.value)) < ( Math.abs(target - val))){
            System.out.println(val);
            val = tree.value;
            
        }
    if(tree.left != null){
        return findClosestValueInBst1(tree.left, target, val);
    }
    if(tree.right != null){
        return findClosestValueInBst1(tree.right, target, val);
    }
    return val;
  }

  static class BST {
    public int value;
    public BST left;
    public BST right;

    public BST(int value) {
      this.value = value;
    }
  }
}

问题树-根=10，节点-> [10,15,22,13,14,5,5,2,1], 目标：12，我的输出：10，正确答案：13,

import java.util.*;

class Program {
     public static int findClosestValueInBst(BST tree, int target) {
         //int closest = Integer.MAX_VALUE;
        // int val = 0;
         int vl = findClosestValueInBst1(tree, target, tree.value);
         return vl;
     }

  public static int findClosestValueInBst1(BST tree, int target, int val) {
    //  System.out.println((closest + "   " + Math.abs(tree.value - target)));
        //c = closest;
        if(( Math.abs(target - tree.value)) < ( Math.abs(target - val))){
            System.out.println(val);
            val = tree.value;
            
        }
    if( target < tree.value && tree.left != null){
        return findClosestValueInBst1(tree.left, target, val);
    } else
            if(target > tree.value && tree.right != null){
        return findClosestValueInBst1(tree.right, target, val);
    } else
    return val;
  }

  static class BST {
    public int value;
    public BST left;
    public BST right;

    public BST(int value) {
      this.value = value;
    }
  }
}

Answer 1

树看起来像这样：

您的代码实际上并未遍历整棵树。此代码：

if(tree.left != null){
    return findClosestValueInBst1(tree.left, target, val);
}
if(tree.right != null){
    return findClosestValueInBst1(tree.right, target, val);
}
return val;

检查左子树是否存在（并忽略右子树）。否则，检查右子树是否存在。否则停止递归。这是因为一旦到达 return 语句，整个方法就停在那里，之后的行不会执行。

所以你的代码总是优先选择左子树而不考虑节点实际存储的数字。所以马上，你走错了方向——你在找 13，而当前节点是 10，更接近的值必须大于 10，即在右子树中。

实际遍历整个树的实现类似于：

public static int findClosestValueInBst(BST tree, int target) { // no need for the val argument!
    int leftClosest = tree.value;
    int rightClosest = tree.value;
    if(tree.left != null){
        leftClosest = findClosestValueInBst1(tree.left, target);
    }
    if(tree.right != null){
        rightClosest = findClosestValueInBst1(tree.right, target);
    }
    if (target - leftClosest < rightClosest - target) {
        return leftClosest;
    } else {
        return rightClosest;
    }
}

但是既然可以更快地完成，为什么还要费心呢？ :)

为什么在给定目标值的情况下尝试在 BST 中找到最接近的值时得到错误答案？

Why am I getting an incorrect answer while trying to find the closest value in a BST given a target value?

java

recursion

tree

binary-search-tree