Valor máximo en cada nivel en un árbol N-ario

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: 

1. Almacene todos los Nodes secundarios del nivel actual en una cola y extraiga los Nodes del nivel actual uno por uno.
2. Encuentre el valor máximo de todos los Nodes reventados del nivel actual.
3. Imprime el valor máximo obtenido en el paso anterior.
4. 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++ 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 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 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# 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

<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)