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