Categorías
Algorithms

LeetCode – Valor del árbol de búsqueda binario más cercano (Java)

Dado un árbol de búsqueda binario no vacío y un valor objetivo, encuentre el valor en la BST que esté más cerca del objetivo.

Solución Java 1: recursividad

Recorre recursivamente la raíz. Cuando el objetivo sea menor que la raíz, vaya a la izquierda; cuando el objetivo es mayor que la raíz, ve a la derecha.

public class Solution {
    int goal;
    double min = Double.MAX_VALUE;
 
    public int closestValue(TreeNode root, double target) {
        helper(root, target);
        return goal;
    }
 
    public void helper(TreeNode root, double target){
        if(root==null)
            return;
 
        if(Math.abs(root.val - target) < min){
            min = Math.abs(root.val-target);
            goal = root.val;
        } 
 
        if(target < root.val){
            helper(root.left, target);
        }else{
            helper(root.right, target);
        }
    }
}

Solución Java 2: iteración

public int closestValue(TreeNode root, double target) {
    double min=Double.MAX_VALUE;
    int result = root.val;
 
    while(root!=null){
        if(target>root.val){
 
            double diff = Math.abs(root.val-target);
            if(diff<min){
                min = Math.min(min, diff);
                result = root.val;
            }
            root = root.right;
        }else if(target<root.val){
 
            double diff = Math.abs(root.val-target);
            if(diff<min){
                min = Math.min(min, diff);
                result = root.val;
            }
            root = root.left;
        }else{
            return root.val;
        }
    }
 
    return result;
}
  LeetCode - Toros y vacas (Java)

Por Programación.Click

Más de 20 años programando en diferentes lenguajes de programación. Apasionado del code clean y el terminar lo que se empieza. ¿Programamos de verdad?

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *