Estoy practicando el desafío de InterviewBit Path to Given Node , pero sigo teniendo problemas:
Primero, si mantengo mi función auxiliar (atravesar) en la estructura de esta manera, cuando ejecuto el código, dice que la atravesación no está definida.
Intenté mover la función dentro solve(A, B) pero luego dice que no obtengo el resultado correcto. Mi código está en la parte inferior.
La pregunta es simple: encuentre la ruta al nodo B en el árbol binario A.
Descripción del problema:
Dado un árbol binario A que contiene N nodos.
Debe encontrar la ruta desde Root hasta un nodo B dado.
NOTA:
No hay dos nodos en el árbol que tengan los mismos valores de datos. Puede suponer que B está presente en el árbol A y que siempre existe un camino.
Entrada de ejemplo
Entrada 1:
un =
1 / \ 2 3 / \ / \ 4 5 6 7B = 5
Entrada 2:
un =
1 / \ 2 3 / \ \ 4 5 6B = 1
Salida de ejemplo
Salida 1:
[1, 2, 5]
Salida 2:
[1]
// Definition for a binary tree node // function TreeNode(data){ // this.data = data // this.left = null // this.right = null // }
module.exports = { //param A : root node of tree //param B : integer //return a array of integers solve : function(A, B){ // traverse tree // each traversal append a new node // if the leaf is not the node, return earlier traversal // like if from left to right we find nothing at all, we return earlier traversal path = traverse(A, B, []); return path; }, traverse: function(node, target, traversal) { if (node) { traversal.push(node.data); if (node.data === target) return traversal; traversal = traverse(node.left, target, traversal); traversal = traverse(node.right, target, traversal); traversal.pop(); } return traversal; }, };Cuando define traverse como una propiedad del objeto exportado, debe llamarlo como this.traverse() . Pero parece mejor hacer la alternativa y definirla como una función local en el ámbito de solve .
El problema con el que luego te encuentras es que incluso cuando encuentras una ruta, aún .pop() de ella, por lo que eso no funcionará.
Al regresar de una llamada recursiva que encontró la ruta, no debe buscar más e inmediatamente devolver esa misma ruta a la persona que llama, quien hará lo mismo, ... hasta que la persona que llamó original obtenga esa ruta.
Otra cosa que debe evitar: no defina la path como una variable global. Declararlo explícitamente con const , let o var .
Así que cambia de la siguiente manera:
solve : function(A, B){ function traverse(node, target, traversal) { if (node) { traversal.push(node.data); if (node.data === target) return traversal; let success = traverse(node.left, target, traversal); if (success) return success; success = traverse(node.right, target, traversal); if (success) return success; traversal.pop(); } } // Declare! let path = traverse(A, B, []); return path;Esto lo arreglará.
Ahora piense cómo puede hacerlo mejor y evite pasar un tercer argumento. Puede utilizar la función de solve de forma recursiva y crear la ruta correcta al retroceder fuera de la recursividad.