Ελέγξτε δεδομένη σειρά μεγέθους n μπορεί να αντιπροσωπεύει BST των n επιπέδων ή όχι


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις αμαζόνα Hulu Intel Juniper Networks Microsoft Ρομπέν των Δασών Ουρλιάζω
Παράταξη Δυαδικό δέντρο αναζήτησης Δυαδικό δέντρο Δέντρο

Δήλωση προβλήματος

Δεδομένου ενός πίνακα με στοιχεία n, ελέγξτε δεδομένο πίνακα μεγέθους n μπορεί να αντιπροσωπεύει BST των επιπέδων n ή όχι. Δηλαδή για να ελέγξετε αν το δέντρο δυαδικής αναζήτησης κατασκευάστηκε χρησιμοποιώντας αυτά n τα στοιχεία μπορούν να αντιπροσωπεύουν ένα BST του n επίπεδα.

Παραδείγματα

arr[] = {10, 8, 6, 9, 3}
false

Επεξήγηση: Από το 8 και το 9 θα τοποθετηθούν στο ίδιο επίπεδο στο BST. Δεν θα είμαστε σε θέση να λάβουμε BST των επιπέδων n.

Ελέγξτε δεδομένη σειρά μεγέθους n μπορεί να αντιπροσωπεύει BST των n επιπέδων ή όχι

arr[] = {18, 12, 6, 9, 7}
true

Επεξήγηση: Εδώ, όπως φαίνεται στην παραπάνω εικόνα, δεν υπάρχουν δύο στοιχεία στο ίδιο επίπεδο. Έτσι, μένουμε με BST μεγέθους n.

 

Προσέγγιση

Μέθοδος 1 (Κατασκευάζοντας το δέντρο)

Ένας από τους τρόπους επίλυσης του παραπάνω προβλήματος είναι να κατασκευαστεί ένα δέντρο με επίπεδα n από τη δεδομένη συστοιχία εισάγοντας την τιμή μικρότερη από τον τρέχοντα κόμβο στα αριστερά του τρέχοντος κόμβου και τιμή μεγαλύτερη από τον τρέχοντα κόμβο στα δεξιά του τρέχοντος κόμβου.
Μετά την κατασκευή του δέντρου, ελέγχουμε αν το δέντρο είναι δέντρο δυαδικής αναζήτησης ή όχι, εάν είναι Δυαδικό δέντρο αναζήτησης, τότε η έξοδος είναι αλήθεια, αλλιώς η έξοδος είναι ψευδής. Εάν είναι αληθές τότε έχουμε ελέγξει εάν μια δεδομένη σειρά μεγέθους n μπορεί να αντιπροσωπεύει BST των επιπέδων n ή όχι και βρήκαμε ότι μπορεί.

1. Initialize root as the first element of the given array. Also initialize temp as root.
2. Traverse the given array starting from index 1(0-based indexing), if the current element is less than temp's value insert it to the left of temp and make temp as left of temp, else insert the current element to the right of temp and make temp as right of temp.
3. After building the tree with n levels using step 2, check if the constructed tree is BST or not. If it is BST return true, else return false.

Ανάλυση πολυπλοκότητας

Χρόνος πολυπλοκότητας = Επί), αφού διασχίζουμε ολόκληρη την είσοδο του μεγέθους n.
Διαστημική πολυπλοκότητα = Ο (η), εδώ δημιουργούμε έναν κόμβο για κάθε στοιχείο σε πίνακα εισαγωγής. Έτσι, η δημιουργία ενός συνόλου κόμβων συμβάλλει στη γραμμική πολυπλοκότητα του χώρου.
όπου n είναι ο αριθμός των στοιχείων στη συστοιχία και h είναι το ύψος του BST, σε αυτήν την περίπτωση h ισούται με n.

Κωδικός JAVA

import java.util.*;
import java.lang.*;
import java.io.*;
 
class CheckGivenArrayOfSizenCanRepresentBSTOfnLevelsOrNot {
    // class to represent the node of a binary tree
    static class Node {
        int data;
        Node left, right;
        public Node(int data) {
            this.data = data;
        }
    }
    // function to check if a tree is BST or not
    private static boolean isBST(Node root, int min, int max) {
        if (root == null) {
            return true;
        }
        return (root.data < max && root.data > min) &&
                isBST(root.left, min, root.data) &&
                isBST(root.right, root.data, max);
    }
    private static Node constructNLevelTree(int[] arr) {
        // initialize root as first element of array
        Node root = new Node(arr[0]);
        // initialize temp as root
        Node temp = root;
        // traverse the array from index 1
        for (int i = 1; i < arr.length; i++) {
            // if current element is less than temp, make temp's left as current element
            // and temp as temp's left
            if (arr[i] < temp.data) {
                temp.left = new Node(arr[i]);
                temp = temp.left;
            }
            // else, make temp's right as current element
            // and temp as temp's right
            else {
                temp.right = new Node(arr[i]);
                temp = temp.right;
            }
        }
        // return the root of tree formed
        return root;
    }
    public static void main(String[] args) {
        // Example 1
        int arr1[] = new int[] {10, 8, 6, 9, 3};
        Node root1 = constructNLevelTree(arr1);
        System.out.println(isBST(root1, Integer.MIN_VALUE, Integer.MAX_VALUE));
        // Example 2
        int arr2[] = new int[] {18, 12, 6, 9, 7};
        Node root2 = constructNLevelTree(arr2);
        System.out.println(isBST(root2, Integer.MIN_VALUE, Integer.MAX_VALUE));
    }
}

 

false
true

Κωδικός 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; 
    } 
};

bool isBST(Node *root, int min, int max) {
    if (root == NULL) {
        return true;
    }
    
    return (root->data < max && root->data > min && 
                isBST(root->left, min, root->data) && 
                isBST(root->right, root->data, max));
}

Node* constructNLevelTree(int *arr, int n) {
    // initialize root as first element of array
    Node *root = new Node(arr[0]);
    // initialize temp as root
    Node *temp = root;
    
    // traverse the array from index 1
    for (int i = 1; i < n; i++) {
        // if current element is less than temp, make temp's left as current element
        // and temp as temp's left
        if (arr[i] < temp->data) {
            temp->left = new Node(arr[i]);
            temp = temp->left;
        } 
        // else, make temp's right as current element
        // and temp as temp's right
        else {
            temp->right = new Node(arr[i]);
            temp = temp->right;
        }
    }
    
    // return the root of tree formed
    return root;
}

int main() {
    // Example 1
    int arr1[] = {10, 8, 6, 9, 3};
    Node *root1 = constructNLevelTree(arr1, sizeof(arr1) / sizeof(arr1[0]));
    if (isBST(root1, INT_MIN, INT_MAX)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }

    // Example 2
    int arr2[] = {18, 12, 6, 9, 7};
    Node *root2 = constructNLevelTree(arr2, sizeof(arr2) / sizeof(arr2[0]));
    if (isBST(root2, INT_MIN, INT_MAX)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    return 0;
}
false
true

Μέθοδος 2 (Χωρίς κατασκευή δέντρου)

Ελέγξτε δεδομένη συστοιχία μεγέθους n μπορεί να αντιπροσωπεύει BST των επιπέδων n ή όχι, το πρόβλημα μπορεί επίσης να επιλυθεί σε συνεχή πολυπλοκότητα χώρου. Η ιδέα είναι να διατηρηθούν δύο μεταβλητές min και max που διασφαλίζουν την κατάσταση των ελάχιστων και μέγιστων τιμών για το επερχόμενο στοιχείο να υπάρχει σε ένα νέο επίπεδο. Δηλαδή, το στοιχείο θα πρέπει να βρίσκεται μεταξύ min και max για να υπάρχει σε ένα νέο επίπεδο, διαφορετικά θα εισαχθεί σε κάποιο υπάρχον επίπεδο στο δέντρο.

1. Initialize min as -infinity and max as infinity.
2. Traverse the given array from index 1(0-based indexing).
3. If the current element is greater than prev element, and also it lies in the range min and max, then update min as prev element.
4. Else if the current element is smaller than prev element and it lies in the range min and max, then update max as prev element.
5. If none of the conditions in step 3 and step 4 is true, return false.
6. At the end of traversal return true.

Ανάλυση πολυπλοκότητας

Πολυπλοκότητα χρόνου = Επί), καθώς διασχίζουμε ολόκληρη την είσοδο του μεγέθους n.
Διαστημική πολυπλοκότητα = Ο (1), αφού δεν δημιουργούμε κόμβους για κάθε στοιχείο. Και έχουμε χρησιμοποιήσει μόνο έναν συγκεκριμένο αριθμό μεταβλητών, έχουμε σταθερή διαστημική λύση.
όπου n είναι ο αριθμός των στοιχείων στον πίνακα.

Κωδικός JAVA

import java.util.*;
import java.lang.*;
import java.io.*;
 
class CheckGivenArrayOfSizenCanRepresentBSTOfnLevelsOrNot {
    private static boolean canRepresent(int[] arr) {
        // initialise min as -infinity and max as infinity
        int min = Integer.MIN_VALUE, max = Integer.MAX_VALUE;
        // traverse the array from index 1
        for (int i = 1; i < arr.length; i++) {
            // if current element is greater than prev and lies in the
            // range min and max, update min as prev
            if (arr[i] > arr[i - 1] && arr[i] > min && arr[i] < max) {
                min = arr[i - 1];
            }
            // else if current element is less than prev and lies in the
            // range min and max, update max as prev
            else if (arr[i] < arr[i - 1] && arr[i] > min && arr[i] < max) {
                max = arr[i - 1];
            }
            // in all other cases return false
            else {
                return false;
            }
        }
        // at the end of the traversal return true
        return true;
    }
    public static void main(String[] args) {
        // Example 1
        int arr1[] = new int[] {10, 8, 6, 9, 3};
        System.out.println(canRepresent(arr1));
        // Example 2
        int arr2[] = new int[] {18, 12, 6, 9, 7};
        System.out.println(canRepresent(arr2));
    }
}
false
true

Κωδικός C ++

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

bool canRepresent(int *arr, int n) {
    // initialise min as -infinity and max as infinity
    int min = INT_MIN, max = INT_MAX;
    
    // traverse the array from index 1
    for (int i = 0; i < n; i++) {
        // if current element is greater than prev and lies in the
        // range min and max, update min as prev
        if (arr[i] > arr[i - 1] && arr[i] > min && arr[i] < max) {
            min = arr[i - 1];
        }
        // else if current element is less than prev and lies in the
        // range min and max, update max as prev
        else if (arr[i] < arr[i - 1] && arr[i] > min && arr[i] < max) {
            max = arr[i - 1];
        }
        // in all other cases return false
        else {
            return false;
        }
    }
    
    // at the end of the traversal return true
    return true;
}

int main() {
    // Example 1
    int arr1[] = {10, 8, 6, 9, 3};
    if (canRepresent(arr1, sizeof(arr1) / sizeof(arr1[0]))) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }

    // Example 2
    int arr2[] = {18, 12, 6, 9, 7};
    if (canRepresent(arr2, sizeof(arr2) / sizeof(arr2[0]))) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    return 0;
}
false
true