چيڪ ڪيل آر جي ماپ واري نمبر ن جي سطح جي BST جي نمائندگي ڪري سگھي ٿو يا نه


تڪليف جي سطح آسان
بار بار پڇڻ ۾ Amazon Hulu اڳوڻن جونيئر نيٽورڪ Microsoft جي رابنڊ Yelp
ڪيريو ثنائي ڳولا وارو وڻ بائنري وڻ وڻن

مسئلي جو بيان

n عناصر سان ٺاھيو ويو ، ھڪڙي لائيٽ جي ترتيب واري ترتيب ڏيو N سطحن جي بي اي ٽي جي نمائندگي ڪري سگھي ٿو يا نه. اهو چيڪ ڪرڻ لاءِ آهي ته ڇا بائنري سرچ وڻ انهن کي استعمال ڪندي ٺاهي وئي آهي n عناصر BST جي نمائندگي ڪري سگھن ٿا ن سطحن تي.

مثال

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

وضاحت: 8 کان ، ۽ 9 بي ايس ٽي ۾ ساڳئي سطح تي رکيا ويندا. اسان کي بي نائين سطح کان BST حاصل نه ٿي سگھندي.

چيڪ ڪيل آر جي ماپ واري نمبر ن جي سطح جي BST جي نمائندگي ڪري سگھي ٿو يا نه

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

وضاحت: هتي ، جيئن مٿي ڏيکاريل تصوير ۾ ڏيکاريل آهي ته ٻه عنصر هڪ ئي سطح تي ناهن. ان ڪري ، اسان ن سائز جي BST سان رھيا آھيون.

 

چرچو

طريقو 1 (وڻ تعمير ڪرڻ سان)

مٿي ڏنل مسئلي کي حل ڪرڻ جو هڪڙو طريقو اهو آهي ته ترتيب ڏنل سرٽي مان ن ليول سان وڻ ٺاهيا وڃن ، موجوده نوڊ جي کاٻي پاسي موجوده نوڊ کان نن valueو قدر داخل ڪيو ۽ موجوده نوڊ جي سا currentي پاسي موجوده نوڊ کان وڌيڪ قدر وڌائين.
وڻ تعمير ڪرڻ کان پوءِ ، اسان چڪاس ڪندا آهيون ته وڻ بائنري سرچ وڻ آهي يا نه ، جيڪڏهن اهو آهي ثنائي ڳولا وارو وڻ، پوء ٻاھر صحيح آھي ، ٻي ٻاھر غلط آھي. جيڪڏهن صحيح آهي ته اسان اهو چڪاس ڪيو آهي ته سائيز جي ڏنل ڏنل قطار ن سطح جي BST جي نمائندگي ڪري سگهي ٿي يا نه ، ۽ اهو معلوم ڪيو ته هو ڪري سگهي ٿي.

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.
خلائي پيچيدگي = اي (ح) ، هتي اسان هر عنصر لاءِ نوڊ ٺاهي رهيا آهيون ان پٽ صف ۾. اھڙي طرح نوڊس جوڙ مڪمل ڪرڻ واري لڪير جي پيچيدگي ۾ حصو وٺندي آھي.
جتي اين صف ۾ عناصر جو تعداد آھي ۽ ايڇ ۾ بي ٽي ايس جي اوچائي آھي h جي برابر آهي n.

جاوا ڪوڊ

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

سي ++ ڪوڊ

#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 (وڻ تعمير ڪرڻ کان سواءِ)

چيڪ ڪيو ويو سي آر سائيز جي ن جي سطحن جي بي سي ايس جي نمائندگي ڪري سگهي ٿو يا نه مسئلو مسلسل خلائي پيچيدگي ۾ حل به ٿي سگهي ٿو. خيال ٻن متغيرن کي برقرار رکڻ جو مقصد آهي وڌ ۽ وڌ کان وڌ جيڪا گهٽ ۾ گهٽ ۽ وڌي ويندڙ قدرن جي حالت کي يقيني بڻائين ته ايندڙ عنصر کي نئين سطح تي موجود ٿيڻ لاءِ. اهو آهي ، عنصر کي گهٽ ۾ گهٽ هجڻ گهرجي گهٽ ۾ گهٽ ۽ موجود هجڻ نئون سطح ۾ ، ٻي صورت ۾ اهو داخل ڪيو ويندو ڪجهه سطح تي موجوده وڻ ۾.

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.

پيچيدگي تجزيي

وقت جي پيچيدگي = اي (ن) ، ڇاڪاڻ ته اسان سائز ن جي سموري انڌول مان گذري رهيا آهيون.
خلائي پيچيدگي = اي (1) ، جئين اسان هر عنصر لاءِ نوڊس نه ٺاهي رهيا آهيون. ۽ صرف خاص تعداد ۾ ڪي پي ڊي استعمال ڪيا آهن ، اسان وٽ مستقل خلا حل آهي
جتي صف ۾ عناصر جو تعداد آهي.

جاوا ڪوڊ

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

سي ++ ڪوڊ

#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