Recorrido de orden de nivel en forma de espiral usando stack y multimap

Dado un árbol binario de N Nodes, la tarea es imprimir el recorrido del orden de niveles en forma de espiral. En forma de espiral, los Nodes del primer y segundo nivel del árbol se imprimen normalmente (de izquierda a derecha), después de lo cual los Nodes de los niveles alternos se imprimen en orden inverso.

Ejemplos:

Entrada: N = 3
      1
     / \
    3   2
Salida: 1 3 2
Explicación:
Nodes en el nivel 0 impresos en orden normal (1)
Nodes en el nivel 1 impresos en orden normal (3, 2)
Por lo tanto, el orden en espiral es (1, 3, 2)

Entrada: N = 5
       10
      /  \
     20  30
    /  \
   40  60
Salida: 10 20 30 60 40
Explicación:
Nodes en el nivel 0 impresos en orden normal (10)
Nodes en el nivel 1 impresos en orden normal (20, 30)
Nodes en el nivel 2 impresos en orden inverso (60, 40)
Por lo tanto, orden en espiral es (10, 20, 30, 60, 40)

Enfoque ingenuo:
Ya se ha discutido un enfoque ingenuo para este problema en este artículo. La idea básica es utilizar la recursividad y una variable bandera, mediante la cual se imprimen los Nodes de niveles alternos en orden inverso y finalmente se obtiene la forma de espiral.
Complejidad temporal: O(N ² )
Espacio auxiliar: O(1)

Enfoque eficiente:
en este enfoque, se utilizan stack y multimap . Un contenedor multimapa en C++ almacena los pares (clave, valor) en orden ascendente, ordenados según la clave. Para cada Node de un árbol dado, si ponemos (nivel, Node) en un mapa múltiple, almacenará estos Nodes ordenados según su nivel.

Por ejemplo, un árbol dado es:

Para este árbol, el mapa múltiple se vería así:

Key(Level)     Value(Element)
0               1
1               2
1               3
2               7
2               6
2               5
2               4

Los pasos detallados de este enfoque son los siguientes:

Atraviese el árbol dado e inserte todos los pares (nivel, Node) en un multimapa y luego atraviese este multimapa.
Si el nivel es impar , imprima los Nodes en el orden en que están presentes en el mapa múltiple.
Si el nivel es par , empuje todos los elementos del nivel actual a una pila, luego extraiga todos los elementos de la pila e imprímalos. Da el orden inverso.

Finalmente, este recorrido de orden de nivel dará como resultado la forma de espiral requerida.

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

// C++ implementation of
// the above approach
  
#include <bits/stdc++.h>
using namespace std;
  
// Tree Node
struct Node {
    int data;
    Node* left;
    Node* right;
};
  
// Utility function to
// create a new Tree Node
Node* newNode(int val)
{
    Node* temp = new Node;
    temp->data = val;
    temp->left = NULL;
    temp->right = NULL;
  
    return temp;
}
  
void printSpiral(Node* root);
  
// Function to build tree
// from given nodes
Node* buildTree(string str)
{
    // Corner Case
    if (str.length() == 0
        || str[0] == 'N')
        return NULL;
  
    // Vector to store nodes
    // after splitting space
    vector<string> ip;
  
    istringstream iss(str);
    for (string str; iss >> str;)
        ip.push_back(str);
  
    // Creating root of the tree
    Node* root = newNode(stoi(ip[0]));
  
    // Push the root to the queue
    queue<Node*> queue;
    queue.push(root);
  
    // Start from second element
    int i = 1;
    while (!queue.empty()
           && i < ip.size()) {
  
        // Get and remove the
        // front of the queue
        Node* currNode = queue.front();
        queue.pop();
  
        // Get the current node's
        // value from the string
        string currVal = ip[i];
  
        // If left child is not null
        if (currVal != "N") {
  
            // Create the left child
            // for the current node
            currNode->left = newNode(stoi(currVal));
  
            // Push it to the queue
            queue.push(currNode->left);
        }
  
        // For the right child
        i++;
        if (i >= ip.size())
            break;
        currVal = ip[i];
  
        // If the right child is not null
        if (currVal != "N") {
  
            // Create the right child
            // for the current node
            currNode->right = newNode(stoi(currVal));
  
            // Push it to the queue
            queue.push(currNode->right);
        }
        i++;
    }
  
    return root;
}
  
// Globally defined multimap
multimap<int, int> m;
  
// Function to fill multimap
void fillMultiMap(Node* root, int level)
{
  
    if (root == NULL)
        return;
  
    else {
        m.insert(pair<int, int>(
            level, root->data));
        fillMultiMap(
            root->left, level + 1);
        fillMultiMap(
            root->right, level + 1);
    }
}
  
void printSpiral(Node* root)
{
    m.clear();
    fillMultiMap(root, 0);
    stack<int> s;
  
    map<int, int>::iterator it
        = m.begin();
  
    // Traversing multimap
    while (it != m.end()) {
  
        // If level is odd
        if ((it->first) % 2 != 0) {
  
            // Printing same order
            while (!s.empty()) {
                cout << s.top() << " ";
                s.pop();
            }
            cout << it->second << " ";
        }
  
        // Otherwise, pushing to stack
        else {
            s.push(it->second);
        }
        it++;
    }
  
    // Pop from stack
    // to get reverse order
    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }
  
    return;
}
  
// Driver code
int main()
{
  
    // Tree input
    string s = "1 2 3 7 6 5 4";
  
    // Build tree form given nodes
    Node* root = buildTree(s);
  
    // Print spiral form
    printSpiral(root);
  
    return 0;
}

Producción:

1 2 3 4 5 6 7

Complejidad temporal: O(NlogN)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por sunilkannur98 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta Cancelar la respuesta