आवर्त स्वरूपात लेव्हल ऑर्डर ट्रॅव्हर्सल


अडचण पातळी मध्यम
वारंवार विचारले अडोब ऍमेझॉन सफरचंद ब्लूमबर्ग फ्लिपकार्ट मायक्रोसॉफ्ट गुण सेवा
रुंदी प्रथम शोध स्टॅक झाड

या समस्येमध्ये आम्ही ए बायनरी ट्री, त्याची स्तरीय ऑर्डर ट्रॉव्हर्सल एक आवर्त स्वरूपात मुद्रित करा.

उदाहरणे

इनपुट

आवर्त स्वरूपात लेव्हल ऑर्डर ट्रॅव्हर्सल
उत्पादन
10 30 20 40 50 80 70 60

सर्पिल फॉर्ममध्ये लेव्हल ऑर्डर ट्रॅव्हर्सलसाठी भोळे दृष्टीकोन

रांगेचा वापर करून सामान्य पातळीची ऑर्डर ट्रव्हर्सल करणे आणि आवश्यक क्रमाने उलट क्रमाने मुद्रित करण्यासाठी स्टॅकचा वापर करणे ही कल्पना आहे.

स्तर 1 उलट नाही, स्तर 2 उलट आहे, स्तर 3 उलट नाही, आणि याप्रमाणे. उलट क्रमाने मुद्रित करावयाच्या सर्व स्तरांसाठी, त्या स्तराचे सर्व घटक एका स्टॅकवर जोडा आणि नंतर ते मुद्रित करा.

  1. एक रांग तयार करा आणि त्यास रूट दाबा. बुलियन व्हेरिएबल रिव्हर्स चुकीचे म्हणून आरंभ करा.
  2. रांग रिक्त नसली तरी चरण पुन्हा करा
  3. रांगेचा आकार म्हणून व्हेरिएबल आकार आरंभ करा. 1 ते आकारात लूप चालवा आणि प्रत्येक पुनरावृत्तीच्या वेळी रांगेतून एखादा घटक काढा आणि जर उलट सत्य असेल तर ते एका स्टॅकवर ढकल, अन्यथा मुद्रित करा. तसेच, काढलेल्या घटकांच्या मुलांना रांगेत ढकलून द्या.
  4. जर उलट सत्य असेल तर स्टॅकचे घटक मुद्रित करा.
  5. नकारात्मक उलट, म्हणजेच जर हे खरे असेल तर ते खोटे बनवा आणि जर ते खोटे असेल तर ते खरे कर.

जावा कोड

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

सी ++ कोड

#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 * एन)
स्पेस कॉम्प्लेक्सिटी = O (n)

सर्पिल फॉर्ममध्ये लेव्हल ऑर्डर ट्रॅव्हर्सलसाठी इष्टतम दृष्टीकोन

लेव्हल ऑर्डर ट्रॉव्हर्सल प्रिंट करण्यासाठी आम्ही दोन स्टॅक वापरतो. त्यांना अनुक्रमे st1 आणि st2 म्हणून कॉल करू.
एसटी 1 सामान्य पातळीवरील ऑर्डर ट्रॉव्हर्सल प्रिंट करते आणि एसटी 2 रिव्हर्स लेव्हल ऑर्डर ट्रॉव्हर्सल प्रिंट करते.

  1. St1 मध्ये रूट पुश करा.
  2. एकतर st1 किंवा st2 रिक्त नसतानाही पुढील गोष्टी करा,
    1. एस 1 रिक्त नसल्यास, घटक पॉप आउट करा आणि मुद्रित करा आणि डाव्या आणि उजव्या मुलांना st2 वर ढकल.
    2. एसटी 2 रिक्त नसतानाही एक घटक पॉप आउट करा आणि ते मुद्रित करा आणि उजव्या आणि डाव्या मुलांना स्ट 1 वर ढकल, उलट क्रम लक्षात घ्या, म्हणजे प्रथम उजव्या मुलाला आणि नंतर डाव्या मुलाला ढकलणे.

जावा कोड

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

सी ++ कोड

#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

सर्पिल फॉर्ममध्ये लेव्हल ऑर्डर ट्रॅव्हर्सलसाठी जटिलता विश्लेषण

वेळ गुंतागुंत = O (n), वेळेच्या अवघडपणाची वरची सीमा (2 * n)
स्पेस कॉम्प्लेक्सिटी = O (n)

संदर्भ