दिलेल्या लेव्हल ऑर्डर ट्रॅव्हर्सलपासून बीएसटी बांधा


अडचण पातळी सोपे
वारंवार विचारले ऍमेझॉन सफरचंद जीई हेल्थकेअर मेटलाइफ मायक्रोसॉफ्ट यूएचजी ऑप्टम केकाटणे
बायनरी शोध वृक्ष बायनरी ट्री रुंदी प्रथम शोध झाड ट्री ट्रॅव्हर्सल

दिले पातळी ऑर्डर आडवा बायनरी शोध वृक्षाचे, बायनरी शोध वृक्ष तयार करण्यासाठी अल्गोरिदम लिहा किंवा बीटीएस आयटीएसकडून स्तरीय ऑर्डर ट्रॉव्हर्सलला द्या.

उदाहरण

इनपुट
पातळी ऑर्डर [] = {18, 12, 20, 8, 15, 25, 5, 9, 22, 31}
उत्पादन

दिलेल्या लेव्हल ऑर्डर ट्रॅव्हर्सलपासून बीएसटी बांधा

ऑर्डरः 5 8 9 12 15 18 20 22 25 31

इनपुट
पातळी ऑर्डर [] = {4, 2, 5, 1, 3, 6}
उत्पादन

दिलेल्या लेव्हल ऑर्डर ट्रॅव्हर्सलपासून बीएसटी बांधा

ऑर्डरः 1 2 3 4 5 6

लेव्हल ऑर्डर ट्रॉव्हर्सलपासून बीएसटी बांधण्यासाठी अल्गोरिदम

लेव्हल ऑर्डर ट्रॅव्हर्सल मधील पहिला घटक नेहमी बायनरी शोधाचा मूळ बनतो झाड. पुढील मूल्य डाव्या नोड किंवा उजव्या नोडच्या मूल्यांच्या आधारे तयार होऊ शकते.

जर पुढील नोड रूटपेक्षा लहान असेल तर ते मूळच्या डाव्या बाजूला घातले जाईल, अन्यथा ते उजवीकडे घातले जाईल.
खालीलप्रमाणे कल्पना आहे की, जर बीएसटीची मूळ शून्य असेल तर मूळ घटक मुळापेक्षा लहान असेल तर त्यास मुळाच्या डाव्या उप-झाडामध्ये योग्य ठिकाणी घाला, अन्यथा त्यास उजव्या उपश्रीमध्ये अयोग्य स्थिती घाला. रूट च्या.

  1. बीएसटीचे मूळ शून्य म्हणून प्रारंभ करा. लेव्हल ऑर्डर ट्रव्हर्सलमध्ये कोणतेही घटक नसल्यास रूट परत करा.
  2. ऑर्डर अ‍ॅरे मधील प्रत्येक घटकासाठी, चरण 3, 4 आणि 5 पुन्हा करा.
  3. जर रूट शून्य असेल तर सद्य घटक मूळ म्हणून बनवा.
  4. अन्यथा जर विद्यमान घटक रूटपेक्षा कमी असेल तर, चरण 3 वर जा, रूट root.left होईल आणि घटक समान राहील.
  5. अन्यथा जर सध्याचा घटक रूटपेक्षा मोठा असेल तर चरण 3 वर जा, रूट रूट होईल. आणि घटक समान राहील.
  6. रिटर्न रूट

लेव्हल ऑर्डर ट्रॅव्हर्सलपासून बीएसटी बांधण्यासाठी जावा कोड

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

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

    // function to print in order traversal of a binary tree
    private static void inorder(Node root) {
        if (root != null) {
            inorder(root.left);
            System.out.print(root.data + " ");
            inorder(root.right);
        }
    }

    private static Node attachNode(Node root, int value) {
        // if root is null, make the current element as root
        if (root == null) {
            root = new Node(value);
            return root;
        }

        // if element is less than root
        if (value < root.data) {
            // attach it to left subtree
            root.left = attachNode(root.left, value);
        } else {
            // attach it to right subtree
            root.right = attachNode(root.right, value);
        }

        // return root
        return root;
    }

    private static Node formBST(int[] levelOrder) {
        // initialize root as null
        Node root = null;

        // for each element attach the node to required position in the BST
        for (int i = 0; i < levelOrder.length; i++) {
            // Step 3 to 5
            root = attachNode(root, levelOrder[i]);
        }

        // return root
        return root;
    }

    public static void main(String[] args) {
        // Example 1
        int levelOrder1[] = new int[] {18, 12, 20, 8, 15, 25, 5, 9, 22, 31};
        Node root1 = formBST(levelOrder1);
        inorder(root1);
        System.out.println();

        // Example 2
        int levelOrder2[] = new int[] {4, 2, 5, 1, 3, 6};
        Node root2 = formBST(levelOrder2);
        inorder(root2);
        System.out.println();
    }
}
5 8 9 12 15 18 20 22 25 31 
1 2 3 4 5 6

लेव्हल ऑर्डर ट्रॉव्हर्सलपासून बीएसटी बांधण्यासाठी सी ++ कोड

#include <iostream> 
#include<vector> 
#include<queue> 
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 print the in-order traversal of a binary tree 
void inOrder(Node *root) { 
    if (root != NULL) { 
        inOrder(root->left); 
        cout<<root->data<<" "; 
        inOrder(root->right); 
    } 
} 

Node* attachNode(Node *root, int value) {
    // if root is null, make the current element as root
    if (root == NULL) {
        root = new Node(value);
        return root;
    }
    
    // if element is less than root
    if (value < root->data) {
        // attach it to left subtree
        root->left = attachNode(root->left, value);
    } else {
        // attach it to right subtree
        root->right = attachNode(root->right, value);
    }
    
    // return root
    return root;
}

Node* formBST(int *levelOrder, int n) {
    // initialize root as null
    Node *root = NULL;
    
    // for each element attach the node to required position in the BST
    for (int i = 0; i < n; i++) {
        // Step 3 to 5
        root = attachNode(root, levelOrder[i]);
    }
    
    // return root
    return root;
}

int main() { 
    // Example 1
    int levelOrder1[] = {18, 12, 20, 8, 15, 25, 5, 9, 22, 31};
    Node *root1 = formBST(levelOrder1, sizeof(levelOrder1) / sizeof(levelOrder1[0]));
    inOrder(root1);
    cout<<endl;

    // Example 2
    int levelOrder2[] = {4, 2, 5, 1, 3, 6};
    Node *root2 = formBST(levelOrder2, sizeof(levelOrder2) / sizeof(levelOrder2[0]));
    inOrder(root2);
    cout<<endl;
    
    return 0; 
}
5 8 9 12 15 18 20 22 25 31 
1 2 3 4 5 6

गुंतागुंत विश्लेषण

वेळ गुंतागुंत = ओ (एन2)
स्पेस कॉम्प्लेक्सिटी = O (n), पुनरावृत्तीमुळे
जेथे n पातळीच्या क्रमाने घटकांची एकूण संख्या आहे अॅरे.

संदर्भ 1     संदर्भ 2