Dado un árbol N-ario que consta de Nodes valorados en el rango [0, N – 1] y una array arr[] donde cada Node i está asociado al valor arr[i] , la tarea es imprimir el valor máximo asociado con cualquier Node en cada nivel del árbol N-ario dado .
Ejemplos:
Entrada: N = 8, Bordes[][] = {{0, 1}, {0, 2}, {0, 3}, {1, 4}, {1, 5}, {3, 6}, { 6, 7}},
arr[] = {4, 2, 3, -5, -1, 3, -2, 6}
Salida: 4 3 6
Explicación:
A continuación se muestra el árbol N-ario dado:El máximo de todos los Nodes del nivel 0 es 4.
El máximo de todos los Nodes del primer nivel es 3.
El máximo de todos los Nodes del segundo nivel es 6.Entrada: N = 10, Bordes[][] = {{0, 1}, {0, 2}, {0, 3}, {1, 4}, {1, 5}, {3, 6}, { 6, 7}, {6, 8}, {6, 9}},
arr[] = {1, 2, -1, 3, 4, 5, 8, 6, 12, 7}
Salida: 1 3 8 12
Explicación:
A continuación se muestra el árbol N-ario dado:El máximo de todos los Nodes del nivel 0 es 1.
El máximo de todos los Nodes del 1er nivel es 3.
El máximo de todos los Nodes del 2º nivel es 8.
El máximo de todos los Nodes del 3er nivel es 12
Enfoque: este problema se puede resolver realizando el recorrido de orden de nivel del árbol dado . Mientras recorre el árbol, procese los Nodes de cada nivel por separado. Para cada nivel que se procesa, calcule el valor máximo de todos los Nodes en el nivel. Siga los pasos a continuación:
- Almacene todos los Nodes secundarios del nivel actual en una cola y extraiga los Nodes del nivel actual uno por uno.
- Encuentre el valor máximo de todos los Nodes reventados del nivel actual.
- Imprime el valor máximo obtenido en el paso anterior.
- Siga los pasos anteriores para cada nivel del Árbol dado e imprima el valor máximo para cada nivel respectivamente.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the maximum value // at each level of N-ary tree int maxAtLevel(int N, int M, vector<int> Value, int Edges[][2]) { // Stores the adjacency list vector<int> adj[N]; // Create the adjacency list for (int i = 0; i < M; i++) { int u = Edges[i][0]; int v = Edges[i][1]; adj[u].push_back(v); } // Perform level order traversal // of nodes at each level queue<int> q; // Push the root node q.push(0); // Iterate until queue is empty while (!q.empty()) { // Get the size of queue int count = q.size(); int maxVal = 0; // Iterate for all the nodes // in the queue currently while (count--) { // Dequeue an node from queue int temp = q.front(); q.pop(); maxVal = max(maxVal, Value[temp]); // Enqueue the children of // dequeued node for (int i = 0; i < adj[temp].size(); i++) { q.push(adj[temp][i]); } } // Print the result cout << maxVal << " "; } } // Driver Code int main() { // Number of nodes int N = 10; // Edges of the N-ary tree int Edges[][2] = { { 0, 1 }, { 0, 2 }, { 0, 3 }, { 1, 4 }, { 1, 5 }, { 3, 6 }, { 6, 7 }, { 6, 8 }, { 6, 9 } }; // Given cost vector<int> Value = { 1, 2, -1, 3, 4, 5, 8, 6, 12, 7 }; // Function Call maxAtLevel(N, N - 1, Value, Edges); return 0; }
Java
// Java program for // the above approach import java.util.*; class GFG{ // Function to find the maximum value // at each level of N-ary tree static void maxAtLevel(int N, int M, int []Value, int Edges[][]) { // Stores the adjacency list Vector<Integer> []adj = new Vector[N]; for (int i = 0; i < adj.length; i++) adj[i] = new Vector<Integer>(); // Create the adjacency list for (int i = 0; i < M; i++) { int u = Edges[i][0]; int v = Edges[i][1]; adj[u].add(v); } // Perform level order traversal // of nodes at each level Queue<Integer> q = new LinkedList<>(); // Push the root node q.add(0); // Iterate until queue is empty while (!q.isEmpty()) { // Get the size of queue int count = q.size(); int maxVal = 0; // Iterate for all the nodes // in the queue currently while (count-- > 0) { // Dequeue an node from queue int temp = q.peek(); q.remove(); maxVal = Math.max(maxVal, Value[temp]); // Enqueue the children of // dequeued node for (int i = 0; i < adj[temp].size(); i++) { q.add(adj[temp].get(i)); } } // Print the result System.out.print(maxVal + " "); } } // Driver Code public static void main(String[] args) { // Number of nodes int N = 10; // Edges of the N-ary tree int Edges[][] = {{0, 1}, {0, 2}, {0, 3}, {1, 4}, {1, 5}, {3, 6}, {6, 7}, {6, 8}, {6, 9}}; // Given cost int []Value = {1, 2, -1, 3, 4, 5, 8, 6, 12, 7}; // Function Call maxAtLevel(N, N - 1, Value, Edges); } } // This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach # Function to find the maximum value # at each level of N-ary tree def maxAtLevel(N, M, Value, Edges): # Stores the adjacency list adj = [[] for i in range(N)] # Create the adjacency list for i in range(M): u = Edges[i][0] v = Edges[i][1] adj[u].append(v) # Perform level order traversal # of nodes at each level q = [] # Push the root node q.append(0) # Iterate until queue is empty while (len(q)): # Get the size of queue count = len(q) maxVal = 0 # Iterate for: all the nodes # in the queue currently while (count): # Dequeue an node from queue temp = q[0] q.remove(q[0]) maxVal = max(maxVal, Value[temp]) # Enqueue the children of # dequeued node for i in range(len(adj[temp])): q.append(adj[temp][i]) count -= 1 # Print the result print(maxVal, end = " ") # Driver Code if __name__ == '__main__': # Number of nodes N = 10 # Edges of the N-ary tree Edges = [ [ 0, 1 ], [ 0, 2 ], [ 0, 3 ], [ 1, 4 ], [ 1, 5 ], [ 3, 6 ], [ 6, 7 ], [ 6, 8 ], [ 6, 9 ] ] # Given cost Value = [ 1, 2, -1, 3, 4, 5, 8, 6, 12, 7 ] # Function Call maxAtLevel(N, N - 1, Value, Edges) # This code is contributed by ipg2016107
C#
// C# program for // the above approach using System; using System.Collections.Generic; class GFG{ // Function to find the // maximum value at each // level of N-ary tree static void maxAtLevel(int N, int M, int []Value, int [,]Edges) { // Stores the adjacency list List<int> []adj = new List<int>[N]; for (int i = 0; i < adj.Length; i++) adj[i] = new List<int>(); // Create the adjacency list for (int i = 0; i < M; i++) { int u = Edges[i, 0]; int v = Edges[i, 1]; adj[u].Add(v); } // Perform level order traversal // of nodes at each level Queue<int> q = new Queue<int>(); // Push the root node q.Enqueue(0); // Iterate until queue is empty while (q.Count != 0) { // Get the size of queue int count = q.Count; int maxVal = 0; // Iterate for all the nodes // in the queue currently while (count-- > 0) { // Dequeue an node from queue int temp = q.Peek(); q.Dequeue(); maxVal = Math.Max(maxVal, Value[temp]); // Enqueue the children of // dequeued node for (int i = 0; i < adj[temp].Count; i++) { q.Enqueue(adj[temp][i]); } } // Print the result Console.Write(maxVal + " "); } } // Driver Code public static void Main(String[] args) { // Number of nodes int N = 10; // Edges of the N-ary tree int [,]Edges = {{0, 1}, {0, 2}, {0, 3}, {1, 4}, {1, 5}, {3, 6}, {6, 7}, {6, 8}, {6, 9}}; // Given cost int []Value = {1, 2, -1, 3, 4, 5, 8, 6, 12, 7}; // Function Call maxAtLevel(N, N - 1, Value, Edges); } } // This code is contributed by 29AjayKumar
Javascript
<script> // Javascript program for the above approach // Function to find the maximum value // at each level of N-ary tree function maxAtLevel(N, M, Value, Edges) { // Stores the adjacency list let adj = new Array(N); for(let i = 0; i < adj.length; i++) adj[i] = []; // Create the adjacency list for(let i = 0; i < M; i++) { let u = Edges[i][0]; let v = Edges[i][1]; adj[u].push(v); } // Perform level order traversal // of nodes at each level let q = []; // Push the root node q.push(0); // Iterate until queue is empty while (q.length > 0) { // Get the size of queue let count = q.length; let maxVal = 0; // Iterate for all the nodes // in the queue currently while (count-- > 0) { // Dequeue an node from queue let temp = q[0]; q.shift(); maxVal = Math.max(maxVal, Value[temp]); // Enqueue the children of // dequeued node for(let i = 0; i < adj[temp].length; i++) { q.push(adj[temp][i]); } } // Print the result document.write(maxVal + " "); } } // Driver code // Number of nodes let N = 10; // Edges of the N-ary tree let Edges = [ [ 0, 1 ], [ 0, 2 ], [ 0, 3 ], [ 1, 4 ], [ 1, 5 ], [ 3, 6 ], [ 6, 7 ], [ 6, 8 ], [ 6, 9 ] ]; // Given cost let Value = [ 1, 2, -1, 3, 4, 5, 8, 6, 12, 7 ]; // Function Call maxAtLevel(N, N - 1, Value, Edges); // This code is contributed by suresh07 </script>
1 3 8 12
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por muskan_garg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA