Преминаване подреждане на ниво под формата на спирала  


Ниво на трудност M
Често задавани в Кирпич Амазонка ябълка Bloomberg Flipkart Microsoft Qualtrics ServiceNow
Широчина Първо търсене Стек Дърво

В този проблем сме дали a двоично дърво, отпечатайте неговото обръщане на ниво под формата на спирала.

Примери  

Вход

Преминаване подреждане на ниво под формата на спирала
Продукция
10 30 20 40 50 80 70 60

Наивен подход за обръщане на нива под формата на спирала  

Идеята е да се направи обиколка на поръчка с нормално ниво, като се използва опашка и да се използва стек за отпечатване на необходимите нива в обратен ред.

Ниво 1 не е обърнато, ниво 2 е обърнато, ниво 3 не е обърнато и т.н. За всички нива, които трябва да бъдат отпечатани в обратен ред, добавете всички елементи от това ниво към стека и след това ги отпечатайте.

  1. Създайте опашка и натиснете корена към нея. Инициализирайте булева променлива обратна като false.
  2. Докато опашката не е празна, повторете стъпките
  3. Инициализирайте променлив размер като размер на опашката. Изпълнете цикъл от 1 до размер и при всяка итерация премахвайте елемент от опашката и ако обратното е вярно, го натиснете в стек, в противен случай го отпечатайте. Също така избутайте децата на премахнатите елементи в опашката.
  4. Ако обратното е вярно, отпечатайте елементите на стека.
  5. Негат реверс, тоест, ако обратното е вярно, направете го фалшиво, а ако обратното е фалшиво, го направете вярно.

Код на JAVA

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Naive {
    // class representing a tree node
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
        }
    }

    private static void spiralOrderTraversal(Node root) {
        if (root == null) {
            return;
        }

        // create a queue for level order traversal
        Queue<Node> queue = new LinkedList<>();
        // create a stack (used to print a level in reverse order)
        Stack<Node> stack = new Stack<>();
        // Initially reverse is false
        boolean reverse = false;
        // add the root to the queue
        queue.add(root);
        
        // Do a normal level order traversal
        while (!queue.isEmpty()) {
            int size = queue.size();
            // Traverse current level
            for (int i = 0; i < size; i++) {
                Node curr = queue.poll();
                // if reverse is true, push the element to stack, else print it
                if (reverse) {
                    stack.push(curr);
                } else {
                    System.out.print(curr.data + " ");
                }

                if (curr.left != null) {
                    queue.add(curr.left);
                }
                if (curr.right != null) {
                    queue.add(curr.right);
                }
            }

            // if this level has to be reversed, print the content of the stack
            if (reverse) {
                while (!stack.isEmpty()) {
                    System.out.print(stack.pop().data + " ");
                }
            }

            // negate reverse
            reverse = !reverse;
        }
    }

    public static void main(String[] args) {
        // Example tree
        Node root = new Node(10);
        root.left = new Node(20);
        root.right = new Node(30);
        root.right.left = new Node(40);
        root.right.right = new Node(50);
        root.right.left.left = new Node(60);
        root.right.right.left = new Node(70);
        root.right.right.right = new Node(80);

        spiralOrderTraversal(root);
    }
}
10 30 20 40 50 80 70 60

C ++ код

#include<bits/stdc++.h> 
using namespace std;

// class representing a tree node
class Node {
    public:
    int data;
    Node *left;
    Node *right;
    
    Node(int d) {
        data = d;
        left = right = NULL;
    }
};

// function to create a new node
Node* newNode(int x) {
    Node *node = new Node(x);
    return node;
}

void spiralOrderTraversal(Node *root) {
    if (root == NULL) {
        return;
    }
    
    // create a queue for level order traversal
    queue<Node*> q;
    // create a stack (used to print a level in reverse order)
    stack<Node*> st;
    // Initially reverse is false
    bool reverse = false;
    // add the root to the queue
    q.push(root);
    
    // Do a normal level order traversal
    while (!q.empty()) {
        int size = q.size();
        // Traverse current level
        for (int i = 0; i < size; i++) {
            Node* curr = q.front();
            q.pop();
            
            // if reverse is true, push the element to stack, else print it
            if (reverse) {
                st.push(curr);
            } else {
                cout<<curr->data<<" ";
            }
            
            if (curr->left != NULL) {
                q.push(curr->left);
            }
            if (curr->right != NULL) {
                q.push(curr->right);
            }
        }
        
        // if this level has to be reversed, print the content of the stack
        if (reverse) {
            while (!st.empty()) {
                cout<<st.top()->data<<" ";
                st.pop();
            }
        }
        
        // negate reverse
        reverse = !reverse;
    }
}

int main() {
    // Example Tree
    Node *root = newNode(10);
    root->left = newNode(20);
    root->right = newNode(30);
    root->right->left = newNode(40);
    root->right->right = newNode(50);
    root->right->left->left = newNode(60);
    root->right->right->left = newNode(70);
    root->right->right->right = newNode(80);

    spiralOrderTraversal(root);
}
10 30 20 40 50 80 70 60

Анализ на сложността за обхождане на нива под формата на спирала

Сложност във времето = На), горната граница на времевата сложност е (4 * n)
Сложност на пространството = О (п)

Вижте също
Първа лоша версия

Оптимален подход за обръщане на нива под формата на спирала  

Използваме два стека, за да отпечатаме обхождането на реда на ниво. Нека ги наречем съответно st1 и st2.
st1 отпечатва обичайното обръщане на порядъка на ниво, а st2 отпечатва обръщането на обратния ред на ниво.

  1. Натиснете корена в st1.
  2. Направете следното, докато st1 или st2 не са празни,
    1. Докато st1 не е празен, извадете елемент и го отпечатайте и натиснете неговите леви и десни деца на st2.
    2. Докато st2 не е празен, извадете елемент и го отпечатайте и избутайте неговите десни и леви деца до st1, забележете обратния ред, т.е. първо натиснете дясното дете и след това лявото дете.

Код на JAVA

import java.util.Stack;

public class LevelOrderTraversalInSpiralForm {
    // class representing a tree node
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
        }
    }

    private static void spiralOrderTraversal(Node root) {
        if (root == null) {
            return;
        }

        // Create two stacks
        Stack<Node> st1 = new Stack<>();
        Stack<Node> st2 = new Stack<>();
        // push the root to st1
        st1.push(root);

        // do the following while either st1 is not empty or st2 is not empty
        while (!st1.isEmpty() || !st2.isEmpty()) {
            // while st1 is not empty
            while (!st1.isEmpty()) {
                // pop the current element and print it
                Node curr = st1.pop();
                System.out.print(curr.data + " ");
                // push its children to st2
                if (curr.left != null)
                    st2.push(curr.left);
                if (curr.right != null)
                    st2.push(curr.right);
            }

            // while st2 is not empty
            while (!st2.isEmpty()) {
                // pop the current element and print it
                Node curr = st2.pop();
                System.out.print(curr.data + " ");
                // Push its right child and left child to st1 respectively
                if (curr.right != null)
                    st1.push(curr.right);
                if (curr.left != null)
                    st1.push(curr.left);
            }
        }

        System.out.println();
    }

    public static void main(String[] args) {
        // Example tree
        Node root = new Node(10);
        root.left = new Node(20);
        root.right = new Node(30);
        root.right.left = new Node(40);
        root.right.right = new Node(50);
        root.right.left.left = new Node(60);
        root.right.right.left = new Node(70);
        root.right.right.right = new Node(80);

        spiralOrderTraversal(root);
    }
}
10 30 20 40 50 80 70 60

C ++ код

#include<bits/stdc++.h> 
using namespace std;

// class representing a tree node
class Node {
    public:
    int data;
    Node *left;
    Node *right;
    
    Node(int d) {
        data = d;
        left = right = NULL;
    }
};

// function to create a new node
Node* newNode(int x) {
    Node *node = new Node(x);
    return node;
}

void spiralOrderTraversal(Node *root) {
    if (root == NULL) {
        return;
    }
    
    // Create two stacks
    stack<Node*> st1;
    stack<Node*> st2;
    // push the root to st1
    st1.push(root);
    
    // do the following while either st1 is not empty or st2 is not empty
    while (!st1.empty() || !st2.empty()) {
        // while st1 is not empty
        while (!st1.empty()) {
            // pop the current element and print it
            Node *curr = st1.top();
            st1.pop();
            cout<<curr->data<<" ";
            // push its children to st2
            if (curr->left != NULL)
                st2.push(curr->left);
            if (curr->right != NULL)
                st2.push(curr->right);
        }
        
        // while st2 is not empty
        while (!st2.empty()) {
            // pop the current element and print it
            Node *curr = st2.top();
            st2.pop();
            cout<<curr->data<<" ";
            // Push its right child and left child to st1 respectively
            if (curr->right != NULL)
                st1.push(curr->right);
            if (curr->left != NULL)
                st1.push(curr->left);
        }
    }
    
    cout<<endl;
}

int main() {
    // Example Tree
    Node *root = newNode(10);
    root->left = newNode(20);
    root->right = newNode(30);
    root->right->left = newNode(40);
    root->right->right = newNode(50);
    root->right->left->left = newNode(60);
    root->right->right->left = newNode(70);
    root->right->right->right = newNode(80);

    spiralOrderTraversal(root);
}
10 30 20 40 50 80 70 60

Анализ на сложността за обхождане на нива под формата на спирала

Сложност във времето = О (п), горната граница на времевата сложност е (2 * n)
Сложност на пространството = О (п)

Вижте също
Най-краткият палиндром

Препратки