Estoy usando la cola para resolver de forma iterativa una pregunta transversal de pedido anticipado de BST. Lo sé para la pila, está invertido y funciona, pero con la cola obtengo la respuesta incorrecta. ¿Por qué? Gracias
var preorderTraversal = function(root) { if (root == null) { return []; } const queue = []; const result = []; queue.unshift(root); while(queue.length > 0) { let current = queue.shift(); result.unshift(current.val); if (current.right) queue.unshift(current.right); if (current.left) queue.unshift(current.left); } return result; };Está utilizando la queue como una pila, ya que cambia los valores dentro y fuera del mismo lado de la matriz, que es lo que hace una pila ("LIFO (último en entrar, primero en salir)"). Así que en realidad funciona, pero como dices al principio, funciona a la inversa porque antepones los valores al resultado. Si los agregara , estaría bien:
var preorderTraversal = function(root) { if (root == null) { return []; } const queue = []; const result = []; queue.unshift(root); while(queue.length > 0) { let current = queue.shift(); result.push(current.val); // Append instead of prepend if (current.right) queue.unshift(current.right); if (current.left) queue.unshift(current.left); } return result; }; // Add the Node class to facilitating creating a binary tree (a binary search tree) class Node { constructor(val) { this.val = val; this.left = this.right = null; } add(val) { if (val < this.val) { if (this.left) this.left.add(val); else this.left = new Node(val); } else { if (this.right) this.right.add(val); else this.right = new Node(val); } } print(tab="") { if (this.right) this.right.print(" " + tab); console.log(tab + this.val); if (this.left) this.left.print(" " + tab); } } // Demo let root = new Node(4); for (let val of [2, 6, 1, 3, 5, 7]) root.add(val); console.log("The tree (with root at the far left): "); root.print(); // Print the tree console.log("preorder traversal: ", ...preorderTraversal(root));Nuevamente, esta es una solución de pila , no una solución de cola , a pesar del nombre de la variable. Los métodos de matriz de JavaScript brindan una interfaz "deque" a las matrices, por lo que puede agregar y eliminar fácilmente elementos de cualquier lado de la matriz.
Si usa exclusivamente push y pop , tendrá un comportamiento de pila, y si los reemplaza con unshift y shift , seguirá teniendo un comportamiento de pila.
Obtendrá un comportamiento de cola cuando use el par push / shift o el par unshift / pop , pero eso no será útil para implementar un recorrido previo al pedido. Eso es lo que usaría para un recorrido de orden de nivel (anchura primero).