Estaba haciendo un problema de algoritmo y encontré este problema en el que resuelves la suma de las profundidades de los nodos (distancia entre un nodo en un BST y la raíz del árbol).
Estaba confundido acerca de dónde desestructuran el nodo y la profundidad de stack.pop() .
¿Cuál es el propósito de esto? ¿Y por qué iterar +1 en profundidad por bucle?
function nodeDepths(root) { console.log("root", root); let depthSum = 0; const stack = [{ node: root, depth: 0 }]; while (stack.length > 0) { const { node, depth } = stack.pop(); console.log("node,", node, "depth", depth); if (node === null) continue; depthSum += depth; stack.push({ node: node.left, depth: depth + 1 }); stack.push({ node: node.right, depth: depth + 1 }); } return depthSum; }Estaba confundido donde desestructuran el nodo y la profundidad de stack.pop(); ¿Cuál es el propósito de esto?
El bucle while necesita tanto las propiedades de node como de depth , y se combinaron en un objeto que se empujó a la pila.
const { node, depth } = stack.pop(); if (node === null) continue; // node--^ v---------depth depthSum += depth; stack.push({ node: node.left, depth: depth + 1 }); // / \ // node----------------+ +----- depth // \ / stack.push({ node: node.right, depth: depth + 1 });¿Y por qué iteran +1 en profundidad por ciclo?
Los hijos están un nivel por debajo de su padre, por lo que agregamos uno.
Ciertamente es posible una versión recursiva más simple de esta función, una en la que no tiene que mantener una pila:
const depthSum = (node, depth = 0) => node == null ? 0 : depth + depthSum (node .left, depth + 1) + depthSum (node .right, depth + 1) const tree = { // Depth value: 'a', // 0 left: { value: 'b', // 1 left: { value: 'c' // 2 }, right: { value: 'd', // 2 left: { value: 'e', // 3 right: { value: 'f' // 4 } } } }, right: { value: 'g', // 1 left: { value: 'h' // 2 }, right: { value: 'i' // 2 } // +___ } // 17 } console .log (depthSum (tree))Este código es más simple y más directo. Pero es menos eficiente y, dependiendo de la profundidad de su árbol, podría encontrarse con limitaciones de profundidad de recursión. El original no está sujeto a eso. Tendría que hacer la llamada para sus propios usos.