ಎರಡು ಕ್ಯೂಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಲೆವೆಲ್ ಆರ್ಡರ್ ಟ್ರಾವೆರ್ಸಲ್


ತೊಂದರೆ ಮಟ್ಟ ಮಧ್ಯಮ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಮೆಜಾನ್ ಪಾದಯಾತ್ರೆ ಮೈಕ್ರೋಸಾಫ್ಟ್ ಮಾರ್ಗನ್ ಸ್ಟಾನ್ಲಿ
ಬೈನರಿ ಟ್ರೀ ಅಗಲ ಮೊದಲ ಹುಡುಕಾಟ ಕ್ಯೂ ಮರ ಟ್ರೀ ಟ್ರಾವೆರ್ಸಲ್

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ

“ಎರಡು ಕ್ಯೂಗಳನ್ನು ಬಳಸುವ ಲೆವೆಲ್ ಆರ್ಡರ್ ಟ್ರಾವೆರ್ಸಲ್” ಸಮಸ್ಯೆ ನಿಮಗೆ ಬೈನರಿ ಮರವನ್ನು ನೀಡಲಾಗಿದೆ ಎಂದು ಹೇಳುತ್ತದೆ, ಅದನ್ನು ಮುದ್ರಿಸಿ ಮಟ್ಟದ ಆದೇಶ ಅಡ್ಡಹಾಯುವಿಕೆ ಸಾಲಿನ ಮೂಲಕ ಸಾಲು.

ಉದಾಹರಣೆಗಳು

ಇನ್ಪುಟ್

ಎರಡು ಕ್ಯೂಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಲೆವೆಲ್ ಆರ್ಡರ್ ಟ್ರಾವೆರ್ಸಲ್

5
11 42
7 9 8
12 23 52 3

ಇನ್ಪುಟ್
ಎರಡು ಕ್ಯೂಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಲೆವೆಲ್ ಆರ್ಡರ್ ಟ್ರಾವೆರ್ಸಲ್

1
2 3
4 5 6

ಎರಡು ಕ್ಯೂಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಲೆವೆಲ್ ಆರ್ಡರ್ ಟ್ರಾವೆರ್ಸಲ್‌ಗಾಗಿ ಅಲ್ಗಾರಿದಮ್

ಎರಡು ಕ್ಯೂಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಲೆವೆಲ್ ಆರ್ಡರ್ ಟ್ರಾವೆರ್ಸಲ್ ಅನ್ನು ಮುದ್ರಿಸಲು, ನಾವು ಮೊದಲು ಮೊದಲ ಕ್ಯೂ (ರೂಟ್) ಅನ್ನು ಮೊದಲ ಕ್ಯೂಗೆ ತಳ್ಳುತ್ತೇವೆ, ಮೊದಲ ಕ್ಯೂನಿಂದ ಒಂದು ಮಟ್ಟವನ್ನು ಹೊರಹಾಕುವಾಗ, ನಾವು ಮುಂದಿನ ಹಂತವನ್ನು ಎರಡನೇ ಕ್ಯೂಗೆ ತಳ್ಳುತ್ತೇವೆ ಮತ್ತು ಎರಡನೇ ಕ್ಯೂನಿಂದ ಒಂದು ಮಟ್ಟವನ್ನು ಹೊರಹಾಕುವಾಗ, ಮುಂದಿನ ಹಂತವನ್ನು ಮೊದಲ ಕ್ಯೂಗೆ ತಳ್ಳಿರಿ. ಎರಡು ಸಾಲುಗಳಲ್ಲಿ ಯಾವುದೂ ಖಾಲಿಯಾಗದವರೆಗೆ ಈ ಪ್ರಕ್ರಿಯೆಯನ್ನು ಪುನರಾವರ್ತಿಸಿ.

  1. ಎರಡು ರಚಿಸಿ ಬಾಲಗಳು q1 ಮತ್ತು q2.
  2. ಮೂಲವನ್ನು q1 ಗೆ ತಳ್ಳಿರಿ.
  3. Q1 ಖಾಲಿಯಾಗಿಲ್ಲ ಅಥವಾ q2 ಖಾಲಿಯಾಗಿಲ್ಲದಿದ್ದರೂ ಹಂತ 4 ಮತ್ತು 5 ಅನ್ನು ಪುನರಾವರ್ತಿಸಿ.
  4. Q1 ಖಾಲಿಯಾಗಿಲ್ಲವಾದರೂ, ಒಂದೊಂದಾಗಿ ಕ್ಯೂನಿಂದ ಅಂಶಗಳನ್ನು ತೆಗೆದುಹಾಕಿ, ಅದನ್ನು ಮುದ್ರಿಸಿ ಮತ್ತು ಅದರ ಮಕ್ಕಳನ್ನು q2 ಗೆ ತಳ್ಳಿರಿ. ಕ್ಯೂ ಖಾಲಿಯಾದ ನಂತರ ಹೊಸ ಸಾಲನ್ನು ಮುದ್ರಿಸಿ.
  5. Q2 ಖಾಲಿಯಾಗಿಲ್ಲವಾದರೂ, ಒಂದೊಂದಾಗಿ ಕ್ಯೂನಿಂದ ಅಂಶಗಳನ್ನು ತೆಗೆದುಹಾಕಿ, ಅದನ್ನು ಮುದ್ರಿಸಿ ಮತ್ತು ಅದರ ಮಕ್ಕಳನ್ನು q1 ಗೆ ತಳ್ಳಿರಿ. ಕ್ಯೂ ಖಾಲಿಯಾದ ನಂತರ ಹೊಸ ಸಾಲನ್ನು ಮುದ್ರಿಸಿ.

ವಿವರಣೆ

ಮೇಲಿನ ಎರಡನೇ ಉದಾಹರಣೆಯಲ್ಲಿ ಮರವನ್ನು ಪರಿಗಣಿಸಿ.

ಹಂತ 1
Q1 ಮತ್ತು q2 ಎಂಬ ಎರಡು ಸಾಲುಗಳನ್ನು ರಚಿಸಿ.
q1 = ಶೂನ್ಯ ಮತ್ತು q2 = ಶೂನ್ಯ

ಹಂತ 2
ಕ್ಯೂ q1 ಗೆ ಮೂಲವನ್ನು ಒತ್ತಿರಿ
q1 = 1 ಮತ್ತು q2 = ಶೂನ್ಯ

ಹಂತ 3
ಕ್ಯೂ 4 ಅಥವಾ q5 ಎರಡೂ ಖಾಲಿಯಾಗಿರದಿದ್ದಾಗ ಹಂತ 1 ಮತ್ತು 2 ಅನ್ನು ಪುನರಾವರ್ತಿಸಿ

ಹಂತ 4 ಮತ್ತು 5
q1 = 2 ಮತ್ತು q2 = ಶೂನ್ಯ

ಪುನರಾವರ್ತನೆ 1
ಮುದ್ರಿಸು 2.
q1 = ಶೂನ್ಯ ಮತ್ತು q2 = 2 -> 3
ಸಾಲು ವಿರಾಮವನ್ನು ಮುದ್ರಿಸಿ.

ಪುನರಾವರ್ತನೆ 2
2 ಮತ್ತು 3 ಅನ್ನು ಮುದ್ರಿಸಿ.
q1 = 4 -> 5 -> 6 ಮತ್ತು q2 = ಶೂನ್ಯ
ಸಾಲು ವಿರಾಮವನ್ನು ಮುದ್ರಿಸಿ.

ಪುನರಾವರ್ತನೆ 3
4, 5 ಮತ್ತು 6 ಅನ್ನು ಮುದ್ರಿಸಿ.
q1 = ಶೂನ್ಯ ಮತ್ತು q2 = ಶೂನ್ಯ
ಸಾಲು ವಿರಾಮವನ್ನು ಮುದ್ರಿಸಿ.

ಎರಡೂ ಸಾಲುಗಳು ಖಾಲಿಯಾಗುತ್ತಿದ್ದಂತೆ, ನಾವು ಇಲ್ಲಿ ನಿಲ್ಲುತ್ತೇವೆ.

ಕೋಡ್

ಎರಡು ಕ್ಯೂಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಲೆವೆಲ್ ಆರ್ಡರ್ ಟ್ರಾವೆರ್ಸಲ್‌ಗಾಗಿ ಜಾವಾ ಕೋಡ್

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

class LevelOrderTraversalUsingTwoQueues {
    // class representing node of a binary tree
    static class Node {
        int data;
        Node left, right;

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

    private static void levelOrderTraversal(Node root) {
        if (root == null) {
            System.out.println();
            return;
        }

        // create two queues q1 and q2
        Queue<Node> q1 = new LinkedList<>();
        Queue<Node> q2 = new LinkedList<>();
        // push the root to queue q1
        q1.add(root);
        
        // while either q1 is not empty or q2 is not empty
        while (!q1.isEmpty() || !q2.isEmpty()) {
            // Pop out a level from q1, print it and push next level to q2
            while (!q1.isEmpty()) {
                // remove a node from q1
                Node curr = q1.poll();
                // print the node
                System.out.print(curr.data + " ");
                // add its children to queue q2
                if (curr.left != null)
                    q2.add(curr.left);
                if (curr.right != null)
                    q2.add(curr.right);
            }
            // print line break
            System.out.println();
            
            // Pop out a level from queue q2 and push next level to q1
            while (!q2.isEmpty()) {
                // remove a node from q2
                Node curr = q2.poll();
                // print the node
                System.out.print(curr.data + " ");
                // add its children to queue q2
                if (curr.left != null)
                    q1.add(curr.left);
                if (curr.right != null)
                    q1.add(curr.right);
            }
            // print line break
            System.out.println();
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // Example Tree 1
        Node root1 = new Node(5);
        root1.left = new Node(11);
        root1.right = new Node(42);
        root1.left.left = new Node(7);
        root1.right.left = new Node(9);
        root1.right.right = new Node(8);
        root1.left.left.left = new Node(12);
        root1.left.left.right = new Node(23);
        root1.right.right.left = new Node(52);
        root1.right.right.right = new Node(3);

        levelOrderTraversal(root1);

        // Example Tree 2
        Node root2 = new Node(1);
        root2.left = new Node(2);
        root2.right = new Node(3);
        root2.left.left = new Node(4);
        root2.left.right = new Node(5);
        root2.right.right = new Node(6);

        levelOrderTraversal(root2);
    }
}
5
11 42
7 9 8
12 23 52 3

1
2 3
4 5 6

ಎರಡು ಕ್ಯೂಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಲೆವೆಲ್ ಆರ್ಡರ್ ಟ್ರಾವೆರ್ಸಲ್‌ಗಾಗಿ ಸಿ ++ ಕೋಡ್

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

// class representing node of a binary tree
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 d) {
    Node *node = new Node(d);
    return node;
}

void levelOrderTraversal(Node *root) {
    if (root == NULL) {
        cout<<endl;
        return;
    }
    
    // create two queues q1 and q2
    queue<Node *> q1;
    queue<Node *> q2;
    // push the root to queue q1
    q1.push(root);
    
    // while either q1 is not empty or q2 is not empty
    while (!q1.empty() || !q2.empty()) {
        // Pop out a level from q1, print it and push next level to q2
        while (!q1.empty()) {
            // remove a node from q1
            Node *curr = q1.front();
            q1.pop();
            // print the node
            cout<<curr->data<<" ";
            // add its children to queue q2
            if (curr->left != NULL)
                q2.push(curr->left);
            if (curr->right != NULL)
                q2.push(curr->right);
        }
        // print line break
        cout<<endl;
        
        // Pop out a level from queue q2 and push next level to q1
        while (!q2.empty()) {
            // remove a node from q2
            Node *curr = q2.front();
            q2.pop();
            // print the node
            cout<<curr->data<<" ";
            // add its children to queue q2
            if (curr->left != NULL)
                q1.push(curr->left);
            if (curr->right != NULL)
                q1.push(curr->right);
        }
        // print line break
        cout<<endl;
    }
    cout<<endl;
}

int main() {
    // Example Tree 1
    Node *root1 = newNode(5);
    root1->left = newNode(11);
    root1->right = newNode(42);
    root1->left->left = newNode(7);
    root1->right->left = newNode(9);
    root1->right->right = newNode(8);
    root1->left->left->left = newNode(12);
    root1->left->left->right = newNode(23);
    root1->right->right->left = newNode(52);
    root1->right->right->right = newNode(3);

    levelOrderTraversal(root1);

    // Example Tree 2
    Node *root2 = newNode(1);
    root2->left = newNode(2);
    root2->right = newNode(3);
    root2->left->left = newNode(4);
    root2->left->right = newNode(5);
    root2->right->right = newNode(6);

    levelOrderTraversal(root2);
    
    return 0;
}
5
11 42
7 9 8
12 23 52 3

1
2 3
4 5 6

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್), ಏಕೆಂದರೆ ನಾವು ಮರದ ಎಲ್ಲಾ ನೋಡ್‌ಗಳ ಮೇಲೆ ಸಂಚರಿಸಿದ್ದೇವೆ. ಹೀಗಾಗಿ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು ರೇಖೀಯವಾಗಿರುತ್ತದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್), ನಾವು ಮರದ ನೋಡ್‌ಗಳ ಮೇಲೆ ಸಂಚರಿಸಿದಂತೆ. ನಾವು ಅವುಗಳನ್ನು ಸರತಿ ಸಾಲಿನಲ್ಲಿ ಸೇರಿಸುತ್ತಿದ್ದೆವು ಮತ್ತು ಆದ್ದರಿಂದ ಸ್ಥಳದ ಸಂಕೀರ್ಣತೆಯೂ ರೇಖೀಯವಾಗಿದೆ.