Dado un árbol binario, imagínese parado en el lado derecho de él, devuelva los valores de los nodos que puede ver ordenados de arriba a abajo. Por ejemplo, dado el siguiente árbol binario,
1 <---
/
2 3 <---
5 <---
Puedes ver [1, 3, 5].
Análisis
Este problema se puede resolver utilizando una cola. En cada nivel del árbol, agregamos el elemento más a la derecha a los resultados.
Solución Java
public List<Integer> rightSideView(TreeNode root) { ArrayList<Integer> result = new ArrayList<Integer>(); if(root == null) return result; LinkedList<TreeNode> queue = new LinkedList<TreeNode>(); queue.add(root); while(queue.size() > 0){ //get size here int size = queue.size(); for(int i=0; i<size; i++){ TreeNode top = queue.remove(); //the first element in the queue (right-most of the tree) if(i==0){ result.add(top.val); } //add right first if(top.right != null){ queue.add(top.right); } //add left if(top.left != null){ queue.add(top.left); } } } return result; } |
Del mismo modo, también podemos usar dos colas, lo que hace que el código sea un poco más legible.
public List<Integer> rightSideView(TreeNode root) { LinkedList<TreeNode> q1 = new LinkedList<>(); LinkedList<Integer> q2 = new LinkedList<>(); ArrayList<Integer> result = new ArrayList<>(); if (root == null) { return result; } q1.offer(root); q2.offer(1); int prev = 0; while (!q1.isEmpty()) { TreeNode h = q1.poll(); int level = q2.poll(); if (level != prev) { result.add(h.val); } if (h.right != null) { q1.offer(h.right); q2.offer(level + 1); } if (h.left != null) { q1.offer(h.left); q2.offer(level + 1); } prev = level; } return result; } |
