Estoy atravesando un árbol binario y acumulando los valores de los nodos visitados en una matriz. Codifique de la siguiente manera:
function Node(val) { this.val = val; this.left = null; this.right = null; } function recurseArray(node,arr=[]){ if(!node){ return; } arr.push(node.val); console.log(`array at node ${node.val}: ${arr}`); recurseArray(node.left,arr); recurseArray(node.right,arr); } let n0 = new Node(0); let n1 = new Node(1); let n2 = new Node(2); n0.left = n1; n0.right = n2; recurseArray(n0);Esperaba obtener este resultado:
array at node 0: 0 array at node 1: 0,1 array at node 2: 0,2 porque pensé que una copia de la versión [0] de la matriz se pasaría por separado a las dos llamadas recurseArray() . Pero en realidad obtengo esta salida:
array at node 0: 0 array at node 1: 0,1 array at node 2: 0,1,2 Parece que, en cambio, es el mismo puntero que se pasa a las llamadas recurseArray() , por lo que los cambios realizados en la llamada node.left aparecen en la llamada node.right . Pasando explícitamente una copia usando:
let leftCopy = [...arr]; let rightCopy = [...arr]; recurseArray(node.left,leftCopy); recurseArray(node.right,rightCopy);da el resultado deseado, pero hacer una copia de la matriz en cada llamada recursiva le dará a esta función una gran complejidad de tiempo y espacio (¿N 2 para ambos, creo?). ¿Hay una forma más eficiente de memoria para hacer esto, o es esta copia explícita la única forma de obtener el resultado que necesito?
una copia de la matriz en cada llamada recursiva le dará a esta función una gran complejidad de tiempo y espacio
Su resultado deseado tiene una complejidad N^2 (en el peor de los casos): para N nodos, registrará N matrices, donde cada matriz tendrá entre 1 y N elementos. Por lo tanto, no hay nada que realmente pueda hacer con el algoritmo para llegar por debajo de eso y obtener el resultado deseado.
Podría usar cadenas en lugar de matrices, pero eso tiene el mismo tipo de problema de complejidad y haría que el código fuera más difícil de entender.
Supongo que una pequeña mejora sería crear solo una nueva matriz cuando necesite cambiar un valor (y un registro), en lugar de crear una nueva matriz incondicionalmente antes de recurrir.
function recurseArray(node,arrParam=[]){ if(!node){ return; } const arr = [...arrParam]; arr.push(node.val); console.log(`array at node ${node.val}: ${arr}`); recurseArray(node.left,arr); recurseArray(node.right,arr); }Este es un algoritmo de retroceso, por lo que es importante que cuando la función recursiva regrese, el estado persistente (en este caso, arr ) se haya restaurado a lo que era cuando se ingresó la función.
Puede hacerlo simplemente haciendo estallar el elemento que empujó antes de regresar:
function recurseArray(node,arr=[]){ if(!node){ return; } arr.push(node.val); console.log(`array at node ${node.val}: ${arr}`); recurseArray(node.left,arr); recurseArray(node.right,arr); arr.pop() }