Algoritmos de Java: codificación de una vista del lado derecho del árbol binario (LeetCode)

Descripción de la tarea:

Dada la root de un árbol binario, imagínate parado en el lado derecho de él. Luego, devuelva los valores de los nodos que puede ver ordenados de arriba a abajo .

Ejemplo 1:

 Input: root = [1,2,3,null,5,null,4] Output: [1,3,4]

Ejemplo 2:

 Input: root = [1,null,3] Output: [1,3]

Ejemplo 3:

 Input: root = [] Output: []

Restricciones:

• El número de nodos en el árbol está en el rango [0, 100] .
• -100 <= Node.val <= 100

Razonamiento:

Diría que es una pregunta bastante popular durante las entrevistas de codificación. A primera vista, parece que es bastante fácil y directo de implementar. Es un sentimiento falso. Crees que sí debido al ejemplo proporcionado. Déjame mostrarte algunos otros ejemplos que no son tan fáciles.

primer ejemplo

¿Qué opinas de este ejemplo? ¿Sigue siendo un camino viable tan obvio para usted? Si tu respuesta es sí, déjame intentarlo de nuevo.

segundo ejemplo

¿Sigue siendo tan obvio? No me parece. Si no está de acuerdo conmigo, probablemente sea una buena idea omitir el resto de este artículo. Para aquellos de ustedes que están confundidos, quédense conmigo.

Introduzcamos el concepto de nivel:

Niveles de un árbol binario

Usando palabras simples, piense en el nivel de un nodo particular en un árbol binario como la profundidad de ese nodo. También podría pensar en ello como: cuántos pasos hacia abajo debe realizar, comenzando desde la raíz del árbol, para llegar a un nodo en particular.

Creo que en este momento te habrás dado cuenta de que necesitamos recorrer cada nodo en un árbol binario provisto, y para cada nodo, debemos responder solo una pregunta. ¿Este nodo es el correcto en su nivel? Es tan simple como eso.

Solución:

Voy a explicar la solución usando un enfoque recursivo. Necesitamos introducir una colección para almacenar nuestras respuestas.

 List<Integer> result = new ArrayList<>(); if (root == null) { return result; }

Podemos devolver inmediatamente una colección vacía si tenemos un nodo raíz nulo.

También introduzco un HashMap para almacenar información, ya sea que visitemos o no un nivel en particular.

 Map<Integer, Boolean> visited = new HashMap<>();

Es hora de introducir el método recursivo con la lógica principal en él.

 private void rightSideView(TreeNode root, List<Integer> result, Map<Integer, Boolean> visited, int currentLevel) { if (root == null) { return; } if (!visited.getOrDefault(currentLevel, false)) { visited.put(currentLevel, true); result.add(root.val); } rightSideView(root.right, result, visited, currentLevel + 1); rightSideView(root.left, result, visited, currentLevel + 1); }

3 cosas en el método son importantes:

1. Necesitamos dejar de explorar árboles en algún momento, lo hacemos si el nodo al que llegamos es nulo

2. Cuando visitamos un nodo, queremos comprobar si es la mejor opción en el nivel específico. Si es así, lo almacenamos y agregamos este nodo a nuestra colección que almacena la respuesta.

3. La forma en que exploramos el árbol también es importante. Es posible que ya haya adivinado que siempre que se nos solicite proporcionar el nodo que mejor se ajuste en cada nivel, a menudo elegiremos ir primero al elemento secundario derecho del nodo actual y luego a la izquierda.

   
   

La solucion completa es esta

 public List<Integer> rightSideView(TreeNode root) { List<Integer> result = new ArrayList<>(); if (root == null) { return result; } Map<Integer, Boolean> visited = new HashMap<>(); rightSideView(root, result, visited, 1); return result; } private void rightSideView(TreeNode root, List<Integer> result, Map<Integer, Boolean> visited, int currentLevel) { if (root == null) { return; } if (!visited.getOrDefault(currentLevel, false)) { visited.put(currentLevel, true); result.add(root.val); } rightSideView(root.right, result, visited, currentLevel + 1); rightSideView(root.left, result, visited, currentLevel + 1); }

Este código nos brinda una complejidad lineal de tiempo y espacio, y funciona bastante bien.

Nos vemos en los próximos artículos 🙃🙃🙃🙃🙃🙃🙃🙃🙃🙃🙃🙃🙃🙃🙃

También publicado aquí.