Recorrido de orden de nivel del árbol N-ario

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:

Imagen

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á presente

Aporte:

Imagen

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.
• Devuelve el vector ans .

A continuación se muestra la implementación del enfoque anterior:

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

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