Estoy trabajando en un desafío de AlgoExpert, ya dediqué tiempo a resolverlo por mi cuenta, vi la conferencia en video y siento que lo entiendo bien, pero mis habilidades con la recursividad y el recorrido del árbol son bastante bajas en este momento (es por eso que Estoy trabajando en ello).
este es el aviso
Escriba una función que tome un árbol de búsqueda binario (BST) y un valor entero de destino y devuelva el valor más cercano a ese valor de destino contenido en el BST. Cada nodo BST tiene un valor entero, un nodo secundario izquierdo y un nodo secundario derecho . Sus hijos son nodos BST válidos en sí mismos o Ninguno / Nulo
META: 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; } // This is the class of the input tree. Do not edit. class BST { constructor(value) { this.value = value; this.left = null; this.right = null; } }El comportamiento hasta ahora es atravesar el nodo 15, pero luego, en lugar de ir al 13, va al 22, por lo que devuelve 10 como el valor posible de cierre en lugar de 13, que tiene un valor absoluto más cercano a 12 que a 10.
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; } // As you can see below this line you are checking target < tree.value // problem is that tree is the root that your surrounding function gets // not the argument that your recursive function gets. // both your condition and your parameter to traverse // need to be inputTree, not tree if (target < tree.value) { console.log('left') traverse(inputTree.left) } else { console.log('right') traverse(inputTree.right) } } traverse(tree) return closest; }Ahora mira el siguiente código:
function findClosestValueInBst(root, target) { let closest = root.value; const traverse = (node) => { if (node === null) return; if (Math.abs(target - closest) > Math.abs(target - node.value)) { closest = node.value; } if (target < node.value) { console.log('left') traverse(node.left) } else { console.log('right') traverse(node.right) } } traverse(root) return closest; }En tales casos, es útil nombrar los parámetros más distintos para que no surja confusión.
Usando los casos de prueba de Nina Scholz, pero lo que veo como una recursividad más simple, podemos hacer esto:
const closer = (v) => (x, y) => Math.abs (x - v) < Math .abs (y - v) ? x : y const findClosestValueInBst = (node, target) => node == null ? Infinity : target == node .value ? node .value : target < node .value ? closer (target) (findClosestValueInBst (node .left, target), node .value) : closer (target) (findClosestValueInBst (node .right, target), node .value) const tree = { value: 10, left: { value: 7, left: { value: 5, left: null, right: null }, right: { value: 8, left: null, right: null } }, right: { value: 13, left: { value: 11, left: null, right: null }, right: { value: 15, left: null, right: null } } }; console .log (findClosestValueInBst (tree, 11)) console .log (findClosestValueInBst (tree, 12)) console .log (findClosestValueInBst (tree, 13)) console .log (findClosestValueInBst (tree, 14)) console .log (findClosestValueInBst (tree, 15)) console .log (findClosestValueInBst (tree, 16)) console .log (tree) .as-console-wrapper {max-height: 100% !important; top: 0} El ayudante closer simplemente elige cuál de los dos números está más cerca de un objetivo, eligiendo arbitrariamente el segundo si están igualmente cerca.
La función principal simplemente se escapa con un valor infinito si el árbol proporcionado es null , y luego se ramifica si nuestro target es igual, menor o mayor que el valor del nodo actual. Si es equal , terminamos y devolvemos el valor del nodo. Si es less than , recurrimos en la rama izquierda y luego elegimos el más cercano de ese resultado y el valor del nodo, y de manera similar, si es greater than , hacemos lo mismo con la rama derecha.
Tenga en cuenta que mis respuestas pueden ser diferentes de las de Nina porque hacemos diferentes elecciones arbitrarias sobre si, por ejemplo, 11 o 13 está más cerca de 12 .
Tal vez esto funcione.
Comprueba el nodo en una sola función y utiliza el último valor con un valor inicial de un valor grande.
Luego encuentra si se encuentra el objetivo y lo devuelve.
De lo contrario, compruebe si el objetivo está dentro.
function findClosestValue(tree, target, last = tree.value) { if (tree === null) return last; if (tree.value === target) return target; if ( last < target && target < tree.value || tree.value < target && target < last ) return Math.abs(target - this.value) < Math.abs(target - last) ? this.value : last; return target < tree.value ? findClosestValue(tree.left, target, tree.value) : findClosestValue(tree.right, target, tree.value); } const tree = { value: 10, left: { value: 7, left: { value: 5, left: null, right: null }, right: { value: 8, left: null, right: null } }, right: { value: 13, left: { value: 11, left: null, right: null }, right: { value: 15, left: null, right: null } } }; console.log(findClosestValue(tree, 11)); console.log(findClosestValue(tree, 12)); console.log(findClosestValue(tree, 13)); console.log(findClosestValue(tree, 14)); console.log(findClosestValue(tree, 15)); console.log(findClosestValue(tree, 16)); console.log(tree); .as-console-wrapper { max-height: 100% !important; top: 0; }