Necesito ayuda para encontrar Lca de dos nodos en el árbol. Entonces, ¿alguien puede explicar cómo usar la recursión para atravesar algún punto y obtener el resultado? Vi muchos ejemplos, pero ninguno de ellos realmente puede ayudarme. Este tipo de problema es realmente nuevo para mí, nunca utilicé la recursividad para atravesar las estructuras del árbol. ¡Agradezco cualquier ayuda!
Así es como se ve mi árbol, y este es uno de muchos ejemplos porque se genera aleatoriamente, y tampoco puedo usar ningún bucle o forEach, solo se permiten métodos de matriz.
const tree = { children: [ { children: [ { children: [], values: [15.667786122807836] } ], values: [35.77483035532576, 1.056418140526505] }, { children: [ { children: [ { children: [], values: [67.83058067285563] } ], values: [98.89823527559626] } ], values: [51.49890385802418, 41.85766285823911] }, ], values: [6.852857017193847, 28.110428400306265, 51.385186145220494]};Esto es lo que estoy tratando de hacer:
const min = graph => { return Math.min(...graph.values, ...graph.children.map(graphNode => min(graphNode))); }; const max = graph => { return Math.max(...graph.values, ...graph.children.map(graphNode => max(graphNode))); }; const distance = graph => { if (!graph.children.length && !graph.values.length) return; const minValue = min(graph); const maxValue = max(graph); const findPath = (graph, key1, key2) => { if (graph.values.includes(key1) || graph.values.includes(key2)) { return graph.values; }; const arr = [graph.values].concat(graph.children.map(graphNode => { return findPath(graphNode, key1, key2); })); return arr; }; const Lca = findPath(graph, minValue, maxValue); return Lca; }Su función findPath devuelve graph.values como el caso base, lo que no ayudará a construir una ruta. En su lugar, los índices de la iteración children.map deben recopilarse como la ruta.
Y luego, cuando tenga tanto el camino al mínimo como el camino al máximo, debe ignorar el prefijo que tienen en común y contar las partes restantes que representan los bordes en el camino entre los dos nodos extremos.
Aquí hay una posible implementación:
// the selector argument is a function that here will be either Math.min or Math.max: function findPath(tree, selector) { const bestOf = (a, b) => selector(a[0], b[0]) === a[0] ? a : b; const recur = (node, path) => node.children.reduce((acc, child, i) => bestOf(acc, recur(child, path.concat(i))), [selector(...node.values), path]); return recur(tree, [])[1]; } function distanceMinMax(tree) { const min = findPath(tree, Math.min), max = findPath(tree, Math.max), common = min.findIndex((child, depth) => max[depth] != child); return min.length + max.length - (common < 0 ? min.length : common) * 2; } // Demo tree: the minimum is 1 and maximum is 10. Distance is 3. const tree = { children: [{ children: [{ children: [], values: [3] }], values: [5, 1] }, { children: [{ children: [{ children: [], values: [9] }], values: [10] }], values: [8, 6] }], values: [2, 4, 7] }; console.log(distanceMinMax(tree)); // 3 Usted escribió que ... "no puede usar ningún bucle o forEach , solo se permiten métodos de matriz".
Esto es realmente una contradicción porque:
.forEach() es un método de matriz;.map() que es bastante similar a .forEach() ;.map() como .includes() representan un bucle;children , ya que cualquier solución tendrá que visitar cada entrada de dicha matriz.