កម្រិតនៃការផ្លាស់ប្តូរលំដាប់ដោយប្រើជួរពីរ


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon ការដំឡើង ក្រុមហ៊ុន Microsoft ក្រុមហ៊ុន Morgan Stanley
មែកធាងគោលពីរ ការស្វែងរកដំបូង ជួរ មែកធាង ការឆ្លងកាត់ដើមឈើ

សេចក្តីថ្លែងការណ៍បញ្ហា។

បញ្ហា“ កម្រិតនៃការផ្លាស់ប្តូរលំដាប់លំដោយដោយប្រើជួរពីរ” ចែងថាអ្នកត្រូវបានគេផ្តល់ឱ្យនូវគោលពីរជាអក្សរគោល កម្រិតលំដាប់ឆ្លងកាត់ បន្ទាត់ដោយបន្ទាត់។

ឧទាហរណ៍

បញ្ចូល

កម្រិតនៃការផ្លាស់ប្តូរលំដាប់ដោយប្រើជួរពីរ

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. ខណៈពេលដែល q1 មិនទទេទេម្តងមួយៗយកធាតុចេញពីជួរបោះពុម្ពវាហើយរុញកូន ៗ របស់វាទៅ q2 ។ ព្រីនជួរថ្មីបន្ទាប់ពីជួរក្លាយជាកន្លែងទទេ។
  5. ខណៈពេលដែល q2 មិនទទេទេម្តងមួយៗយកធាតុចេញពីជួរបោះពុម្ពវាហើយរុញកូន ៗ របស់វាទៅ q1 ។ ព្រីនជួរថ្មីបន្ទាប់ពីជួរក្លាយជាកន្លែងទទេ។

ការពន្យល់

ពិចារណាដើមឈើនៅក្នុងឧទាហរណ៍ទីពីរខាងលើ។

1 ជំហាន
បង្កើតជួរពីរ q1 និង q2 ។
q1 = មោឃៈនិង q2 = មោឃៈ

2 ជំហាន
រុញឫសទៅជួរជួរទី ១
q1 = ១ និង q1 = មោឃៈ

3 ជំហាន
ធ្វើជំហានទី ៤ និង ៥ ម្តងទៀតខណៈពេលដែលជួរ q4 ឬ q5 មិនទទេ

ជំហានទី ៤ និងទី ៥
q1 = ១ និង q2 = មោឃៈ

ការបែងចែក ១
បោះពុម្ព ២ ។
q1 = null និង q2 = ២ -> ៣
បោះពុម្ពបំបែកបន្ទាត់។

ការបែងចែក ១
បោះពុម្ពទី ២ និងទី ៣ ។
q1 = ៤ -> ៥ -> ៦ និង q២ = គ្មាន
បោះពុម្ពបំបែកបន្ទាត់។

ការបែងចែក ១
បោះពុម្ព ៤, ៥ និង ៦ ។
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

លេខកូដ C ++ សម្រាប់ការផ្លាស់ប្តូរលំដាប់ថ្នាក់ដោយប្រើជួរពីរ

#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

ការវិភាគស្មុគស្មាញ

ស្មុគស្មាញពេលវេលា

O (N), ចាប់តាំងពីយើងបានឆ្លងកាត់ថ្នាំងទាំងអស់នៅក្នុងមែកធាង។ ដូច្នេះពេលវេលាស្មុគស្មាញគឺលីនេអ៊ែរ។

ភាពស្មុគស្មាញនៃលំហ

O (N), ដូចដែលយើងបានឆ្លងកាត់ថ្នាំងនៅក្នុងមែកធាង។ យើងក៏បានបញ្ចូលពួកវាទៅក្នុងជួរហើយដូច្នេះភាពស្មុគស្មាញនៃលំហក៏មានលីនេអ៊ែរផងដែរ។