Обход порядка уровней в спиральной форме с использованием стека и мульти-карты

Опубликовано: 1 Января, 2022

Для двоичного дерева из N узлов задача состоит в том, чтобы распечатать обход порядка уровней в спиральной форме. В спиральной форме узлы первого и второго уровня дерева печатаются нормально (слева направо), после чего узлы на других уровнях печатаются в обратном порядке.

Примеры:

Input: N = 3
      1
     / 
    3   2
Output: 1 3 2
Explanation:
Nodes at level 0 printed in normal order (1)
Nodes at level 1 printed in normal order (3, 2)
Hence, spiral order is (1, 3, 2)
Input: N = 5
       10
      /  
     20  30
    /  
   40  60
Output: 10 20 30 60 40
Explanation:
Nodes at level 0 printed in normal order (10)
Nodes at level 1 printed in normal order (20, 30)
Nodes at level 2 printed in reverse order (60, 40)
Hence, spiral order is (10, 20, 30, 60, 40)

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Наивный подход:
Наивный подход к этой проблеме уже обсуждался в этой статье. Основная идея состоит в том, чтобы использовать рекурсию и переменную флага, с помощью которой узлы альтернативных уровней печатаются в обратном порядке и, наконец, получается спиральная форма.
Временная сложность: O (N ² )
Вспомогательное пространство: O (1)

Эффективный подход:
В этом подходе используются стек и мульти-карта . Контейнер с несколькими картами в C ++ хранит пары (ключ, значение) в возрастающем порядке, отсортированные по ключу. Для каждого узла данного дерева, если мы поместим (уровень, узел) в мульти-карту, то он сохранит эти узлы, отсортированные по их уровню.

Например, данное дерево:

Для этого дерева мульти-карта будет выглядеть так:

Ключевое (Уровень) Значение (Элемент)
0 1
1 2
1 3
2 7
2 6
2 5
2 4

Подробные шаги этого подхода следующие:

Пройдите по заданному дереву и вставьте все пары (уровень, узел) в мульти-карту, а затем пройдитесь по этой мульти-карте.
Если уровень нечетный , распечатайте узлы в том порядке, в котором они присутствуют на мульти-карте.
Если уровень четный , поместите все элементы текущего уровня в стек, затем вытолкните все элементы из стека и распечатайте их. Дает обратный порядок.

Наконец, этот обход порядка уровней приведет к требуемой форме спирали.

Ниже представлена реализация описанного выше подхода:

 // C++ implementation of
 // the above approach
 
#include <bits/stdc++.h>
 using namespace std;
 
// Tree Node
 struct Node {
    data; int
    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, level) int
 {
 
    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;
 }

Выход:

1 2 3 4 5 6 7

Сложность времени: O (NlogN)
Вспомогательное пространство: O (N)

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене.

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Олимпиады по программированию Алгоритмы

Обход порядка уровней в спиральной форме с использованием стека и мульти-карты

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

РЕКОМЕНДУЕМЫЕ СТАТЬИ