Recorrido del Árbol de Búsqueda Binaria – Encontrar Valor más Cercano
Estoy trabajando en un desafío de AlgoExpert, ya le he dedicado tiempo para resolverlo por mi cuenta, he visto una conferencia en video sobre él y siento que tengo una buena comprensión, pero mis habilidades con la recursividad y el recorrido de árboles son bastante bajas en este momento (es por eso que estoy trabajando en ello).
Esta es la tarea:
Escriba una función que reciba un árbol binario de búsqueda (BST) y un valor entero objetivo y devuelva el valor más cercano a ese valor objetivo contenido en el BST. Cada nodo de BST tiene un valor entero, un nodo hijo izquierdo y un nodo hijo derecho. Los hijos son nodos BST válidos en sí mismos o None / Null.
OBJETIVO: 12
Esta es mi solución hasta ahora:
function findClosestValueInBst(tree, target) {
let closest = tree.value;
const traverse = (inputTree) => {
if (inputTree === null) return;
if (Math.abs(target - closest) > Math.abs(target - inputTree.value)) {
closest = inputTree.value;
}
if (target < tree.value) {
console.log('left')
traverse(inputTree.left)
} else {
console.log('right')
traverse(inputTree.right)
}
}
traverse(tree)
return closest;
}
// Esta es la clase del árbol de entrada. No editar.
class BST {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
El comportamiento hasta ahora es, recorre hasta el nodo 15, pero luego, en lugar de ir a 13, va a 22, por lo que devuelve 10 como el valor posible más cercano en lugar de 13, que tiene un valor absoluto más cercano a 12 que 10.
davy.ai
No estoy seguro de qué estoy haciendo mal. Cualquier ayuda sería apreciada.
Parece que estás en el camino correcto con tu solución. Parece que estás usando un enfoque recursivo para recorrer el árbol y encontrar el valor más cercano al objetivo.
El problema con tu código es que no estás recorriendo el árbol correctamente. Solo estás recorriendo el lado derecho del árbol, por lo que estás perdiendo el lado izquierdo del árbol. Para solucionar esto, debes agregar una declaración “else” a tu declaración “if” que verifique si el objetivo es menor que el valor del árbol. Esta declaración “else” debe recorrer el lado izquierdo del árbol.
Aquí hay un ejemplo de cómo debería verse tu código:
ahora, si el objetivo es menor que el valor del árbol, el código recorrerá el lado izquierdo del árbol. esto debería solucionar el problema que estás teniendo. {=”” console.log=”” (‘izquierda’)=”” traverse=”” (inputtree.left)=”” }=”” else=”” {=”” console.log=”” (‘derecha’)=”” traverse=”” (inputtree.right)=”” }=”” }=”” traverse=”” (árbol)=”” return=”” máscercano;=”” }=”” esta=”” es=”” la=”” clase=”” del=”” árbol=”” de=”” entrada.=”” no=”” edite.=”” clase=”” bst=”” {=”” constructor=”” (valor)=”” {=”” this.valor=”valor;” this.izquierda=”nulo;” this.derecha=”nulo;” }=”” }=”” “`=”” ahora,=”” si=”” el=”” objetivo=”” es=”” menor=”” que=”” el=”” valor=”” del=”” árbol,=”” el=”” código=”” recorrerá=”” el=”” lado=”” izquierdo=”” del=”” árbol.=”” esto=”” debería=”” solucionar=”” el=”” problema=”” que=”” estás=””></árbol.valor) {
console.log (‘izquierda’)
traverse (inputtree.left)
} else {
console.log (‘derecha’)
traverse (inputtree.right)
}
}
traverse (árbol)
return máscercano;
}
// esta es la clase del árbol de entrada. no edite.
clase bst {
constructor (valor) {
this.valor = valor;
this.izquierda = nulo;
this.derecha = nulo;
}
}
“`
ahora, si el objetivo es menor que el valor del árbol, el código recorrerá el lado izquierdo del árbol. esto debería solucionar el problema que estás teniendo.>