Dado un árbol N-ario. La tarea es imprimir el recorrido del orden de niveles del árbol donde cada nivel estará en una nueva línea.
Ejemplos:
Aporte:
Salida:
1
3 2 4
5 6
Explicación: En el nivel 1: solo 1 está presente.
En el nivel 2: 3, 2, 4 está presente
En el nivel 3: 5, 6 está presenteAporte:
Salida:
1
2 3 4 5
6 7 8 9 10
11 12 13
14
Explicación: Para el ejemplo anterior, hay 5 niveles presentes en el árbol n-ario.
En el nivel 1: solo 1 está presente.
En el nivel 2: 2, 3, 4, 5 está presente.
En el nivel 3: 6, 7, 8, 9, 10 está presente
En el nivel 4: 11, 12, 13 está presente
En el nivel 5: – 14 está presente
Enfoque 1: Uso de BFS
El enfoque del problema es usar Level Order Traversal y almacenar todos los niveles en una array 2D donde cada uno de los niveles se almacena en una fila diferente.
Siga los pasos a continuación para implementar el enfoque:
- Cree un vector ans y temp para almacenar el recorrido de orden de nivel del árbol N-ario.
- Empuje el Node raíz en la cola .
- Ejecute un bucle while hasta que la cola no esté vacía:
- Determine el tamaño del nivel actual, que es el tamaño de la cola (digamos N ):
- Ejecutar un bucle para i = 1 a N
- En cada paso, elimine el Node frontal (digamos cur ) y envíe sus datos a la temperatura como parte del nivel actual.
- Empuja a todos los hijos de cur a la cola.
- Empuje la temperatura en el vector ans final que almacena los diferentes niveles en diferentes filas.
- Determine el tamaño del nivel actual, que es el tamaño de la cola (digamos N ):
- Devuelve el vector ans .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for above implementation #include <bits/stdc++.h> using namespace std; struct Node { char val; vector<Node*> children; }; // Utility function to create a new tree node Node* newNode(int key) { Node* temp = new Node; temp->val = key; return temp; } // Function for level order traversal for n-array tree vector<vector<int> > levelOrder(Node* root) { vector<vector<int> > ans; if (!root) cout << "N-Ary tree does not any nodes"; // Create a queue namely main_queue queue<Node*> main_queue; // Push the root value in the main_queue main_queue.push(root); // Create a temp vector to store the all the node values // present at a particular level vector<int> temp; // Run a while loop until the main_queue is empty while (!main_queue.empty()) { // Get the front of the main_queue int n = main_queue.size(); // Iterate through the current level for (int i = 0; i < n; i++) { Node* cur = main_queue.front(); main_queue.pop(); temp.push_back(cur->val); for (auto u : cur->children) main_queue.push(u); } ans.push_back(temp); temp.clear(); } return ans; } // Driver code int main() { Node* root = newNode(1); root->children.push_back(newNode(3)); root->children.push_back(newNode(2)); root->children.push_back(newNode(4)); root->children[0]->children.push_back(newNode(5)); root->children[0]->children.push_back(newNode(6)); // LevelOrderTraversal obj; vector<vector<int> > ans = levelOrder(root); for (auto v : ans) { for (int x : v) cout << x << " "; cout << endl; } return 0; } // This code is contributed by Aditya Kumar (adityakumar129)
Java
import java.util.*; public class Main { static class Node { public int val; public Vector<Node> children; public Node(int key) { val = key; children = new Vector<Node>(); } } // Utility function to create a new tree node static Node newNode(int key) { Node temp = new Node(key); return temp; } // Function for level order traversal for n-array tree static List<List<Integer> > levelOrder(Node root) { List<List<Integer> > ans = new ArrayList<>(); if (root == null) System.out.println( "N-Ary tree does not any nodes"); // Create one queue main_queue Queue<Node> main_queue = new LinkedList<>(); // Push the root value in the main_queue main_queue.offer(root); // Traverse the N-ary Tree by level while (!main_queue.isEmpty()) { // Create a temp vector to store the all the // node values present at a particular level List<Integer> temp = new ArrayList<>(); int size = main_queue.size(); // Iterate through the current level for (int i = 0; i < size; i++) { Node node = main_queue.poll(); temp.add(node.val); for (Node child : node.children) { main_queue.offer(child); } } ans.add(temp); } return ans; } // Utility function to print the level order traversal public static void printList(List<List<Integer> > temp) { for (List<Integer> it : temp) { for (Integer et : it) System.out.print(et + " "); System.out.println(); } } public static void main(String[] args) { Node root = newNode(1); (root.children).add(newNode(3)); (root.children).add(newNode(2)); (root.children).add(newNode(4)); (root.children.get(0).children).add(newNode(5)); (root.children.get(0).children).add(newNode(6)); List<List<Integer> > ans = levelOrder(root); printList(ans); } } // This code is contributed by Sania Kumari Gupta
1 3 2 4 5 6
Complejidad Temporal: O(V) donde V es el número de Nodes
Espacio Auxiliar: O(V)
Enfoque 2: Uso de DFS
El enfoque del problema es usar Level Order Traversal usando DFS y almacenar todos los niveles en una array 2D donde cada uno de los niveles se almacena en una fila diferente.
- La función LevelOrder actualizará ans con el valor actual, empujándolo con un nuevo subvector si uno que coincida con el nivel no está presente en ans.
- La función aumentará el nivel en 1;
- Se llamará recursivamente a todos los hijos;
- Retrocederá el nivel.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for above implementation #include <bits/stdc++.h> using namespace std; vector<vector<int> > ans; int level = 0; struct Node { char val; vector<Node*> children; }; Node* newNode(int key) { Node* temp = new Node; temp->val = key; return temp; } void levelOrder(Node *root) { if (ans.size() == level) ans.push_back({root->val}); else ans[level].push_back(root->val); level++; for (Node *n: root->children) levelOrder(n); level--; } int main() { Node* root = newNode(1); root->children.push_back(newNode(3)); root->children.push_back(newNode(2)); root->children.push_back(newNode(4)); root->children[0]->children.push_back(newNode(5)); root->children[0]->children.push_back(newNode(6)); // LevelOrderTraversal obj; levelOrder(root); for (auto v : ans) { for (int x : v) cout << x << " "; cout << endl; } return 0; }
1 3 2 4 5 6
Complejidad temporal: O(V)
Espacio auxiliar: O(V)
Publicación traducida automáticamente
Artículo escrito por adityakumar129 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA