Verilən Səviyyə Sifarişinin Keçidindən BST qurun

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon alma GE Healthcare MetLife microsoft UHG Optum Vəngilti
İkili Axtarış Ağacı İkili ağac Genişlik İlk Axtarış Ağac Ağacın keçidiBaxılıb 79

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Verilmişdir səviyyə sifarişinin kəsişməsi ikili axtarış ağacından, ikili axtarış ağacını və ya BST-ni verilən səviyyə keçidindən BST qurmaq üçün bir alqoritm yazın.

misal

Input
levelOrder [] = {18, 12, 20, 8, 15, 25, 5, 9, 22, 31}
Buraxılış

Verilən Səviyyə Sifarişinin Keçidindən BST qurunPin

Sifarişlə: 5 8 9 12 15 18 20 22 25 31

Input
levelOrder [] = {4, 2, 5, 1, 3, 6}
Buraxılış

Verilən Səviyyə Sifarişinin Keçidindən BST qurunPin

Sifarişlə: 1 2 3 4 5 6

Səviyyə cərəyanından BST qurma alqoritmi

Səviyyə keçidindəki ilk element həmişə ikili axtarışın kökünə çevrilir Ağac. Növbəti dəyər, dəyərindən asılı olaraq sol nodu və ya sağ nodu təşkil edə bilər.

Növbəti düyün kökündən sola qoyulandan kökdən kiçikdirsə, başqa bir şey sağa daxil ediləcəkdir.
Fikir aşağıdakı kimidir, əgər BST-nin kökü boşdursa, cari elementin kökündən kiçik olduğunu əmələ gətirin, sonra kökün sol alt ağacındakı uyğun yerə əlavə edin, əksinə sağ alt ağacda uyğun olmayan bir vəziyyətə qoyun. kök.

  1. BST kökünü null olaraq başladın. Səviyyə düzəlişində heç bir element yoxdursa, kök qaytarın.
  2. LevelOrder massivindəki hər element üçün 3, 4 və 5-ci addımları təkrarlayın.
  3. Kök boşdursa, cari elementi kök kimi düzəldin.
  4. Cari element kökdən azdırsa, başqa bir halda 3-cü addıma keçin, kök root.left olur və element eyni qalır.
  5. Cari element kökdən böyükdürsə, başqa bir şəkildə 3-cü addıma keçin, kök kök olur. Sağ və element eyni qalır.
  6. Kökə qayıdın.

Səviyyə düzəlişindən BST qurmaq üçün JAVA Kod

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

Səviyyə sifarişindən BST qurmaq üçün C ++ kodu

#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

Mürəkkəblik təhlili

Zaman Mürəkkəbliyi = O (n)2)
Kosmik Mürəkkəblik = O (n), rekursiyaya görə
burada n səviyyə sırasındakı elementlərin ümumi sayıdır array.

İstinad1     arayış2

Crack Sistemi Dizayn Müsahibələri
Translate »