Spiral formada səviyyə əmri

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon alma Bloomberg Flipkart microsoft Kvalifikasiya XidmətNow
Genişlik İlk Axtarış Qalaq AğacBaxılıb 32

Bu problemdə bir ikili ağac, səviyyə sifarişini spiral şəklində çap edin.

Nümunələr

Input

Spiral formada səviyyə əmriPin
Buraxılış
10 30 20 40 50 80 70 60

Spiral formada səviyyə sifarişinin keçməsi üçün sadəlövh yanaşma

Fikir, bir sıra istifadə edərək normal səviyyəli sifariş keçidini etmək və lazımi səviyyələri tərs qaydada çap etmək üçün bir yığın istifadə etməkdir.

Səviyyə 1 tərs çevrilmir, səviyyə 2 tərs, səviyyə 3 geri çevrilmir və s. Ters qaydada yazdırılmalı olan bütün səviyyələr üçün bu səviyyə bütün elementlərini bir yığına əlavə edin və sonra çap edin.

  1. Bir növbə yaradın və kökü ona itələyin. Boole dəyişənini tərs olaraq yalan olaraq başlatın.
  2. Növbə boş olmasa da, addımları təkrarlayın
  3. Dəyişən ölçünü növbənin ölçüsü kimi başladın. 1-dən ölçüyə qədər bir döngə işlədin və hər təkrarlanmada bir elementi növbədən çıxarın və əksi doğrudursa, onu yığına itələyin, əksinə çap edin. Ayrıca, silinmiş elementlərin uşaqlarını növbəyə itələyin.
  4. Tersi doğrudursa, yığının elementlərini yazdırın.
  5. Ters bax, yəni tersi doğrudursa, yalan et, tersi yalnışsa, onu deqiq et.

JAVA Kodu

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

#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

Spiral formada səviyyə sifarişinin keçməsi üçün komplekslik analizi

Zaman Mürəkkəbliyi = O (n), zaman mürəkkəbliyinin yuxarı həddi (4 * n)
Kosmik Mürəkkəblik = O (n)

Spiral formada səviyyə sifarişinin keçməsi üçün optimal yanaşma

Səviyyə sifariş keçidini çap etmək üçün iki yığından istifadə edirik. Onları sırasıyla st1 və st2 adlandıraq.
st1 adi səviyyə keçidini və st2 tərs səviyyə sifarişini çap edir.

  1. Kökü st1-də itələyin.
  2. St1 və ya st2 boş olmadıqda aşağıdakıları edin,
    1. St1 boş olmasa da, bir elementi açın və yazdırın və sol və sağ uşaqlarını st2-yə itələyin.
    2. St2 boş olmasa da, bir elementi açın və yazdırın və sağ və sol uşaqlarını st1-ə itələyin, tərs sıraya diqqət yetirin, yəni əvvəlcə sağ uşağı və sonra sol uşağı itələyin.

JAVA Kodu

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

#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

Spiral formada səviyyə sifarişinin keçməsi üçün komplekslik analizi

Zaman Mürəkkəbliyi = O (n)zaman mürəkkəbliyinin yuxarı həddi (2 * n)
Kosmik Mürəkkəblik = O (n)

References

Translate »