java - 为什么在给定目标值的情况下尝试在 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;
    }
  }
}

问题树- Root = 10，Nodes-> [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;
    }
  }
}

标签： javarecursiontreebinary-search-tree

Answer 1

树看起来像这样：

     10
     /\
    5  15
   /   /\
  2   13 22
 /     \
1      14

您的代码实际上并没有遍历整个树。这段代码：

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;
    }
}

但是，当您可以更快地做到这一点时，为什么还要麻烦呢？:)