बाइनरी खोज ट्री लीटकोड समाधानमा खोजी गर्नुहोस्


कठिनाई तह सजिलो
बारम्बार सोधिन्छ एप्पल आईबीएम
बाइनरी खोज रूख

यो समस्यामा, हामीलाई एक दिइन्छ बाइनरी खोज रूख र पूर्णांक हामीले नोडको ठेगाना दिइएको पूर्णाger्कसँग मिल्दो हुनु पर्छ। जाँचको रूपमा, हामीले उप-रूखको प्रिअर्डर ट्राभर्सल प्रिन्ट गर्नु पर्छ जुन यस नोडलाई रुटको रूपमा छ। यदि रूखमा दिइएको पूर्णांक जस्तो कुनै मान छैन भने, हामीले फर्कनु पर्छ खालीअर्थात्, खाली रूख।

उदाहरणका

     2
    
  /     \

1         3

             \

               4


Target Value = 3
3 4
     5

  /      \

1         10 


Target Value = 4
Empty BST

स्पष्टीकरण # १

BST मा 3 मान सहित नोड समावेश छ, त्यसैले हामी यसको उप-रूख फर्काउँछौं र यसको प्रिअर्डर ट्रभर्सल प्रिन्ट गर्दछ।

स्पष्टीकरण # १

BST ले मान n को साथ कुनै नोड समावेश गर्दैन, त्यसैले हामी NULL फिर्ता गर्छौं र “खाली BST” प्रिन्ट गर्दछौं।

दृष्टिकोण (रिकर्सिभ)

आउनुहोस् हामी कसरी सोच्दछौं कि कसरी समस्या यस मामलामा उप-समस्यामा निर्भर गर्दछ। मानौं यदि हाम्रो प्रकार्यले नोडको ठेगाना लक्षित मानको साथ फिर्ता गर्दछ, यदि भेटियो भने। हामी रूखको जराबाट शुरू गर्दछौं। यदि यो नोड हो खाली, यो स्पष्ट छ कि हामी बाइनरी खोज रूखको अन्त्यमा पुगेका छौं र त्यसैले लक्षित मानको साथ कुनै नोड छैन। त्यसो भए हामी फर्कियौं खाली। त्यस्तै, हामी नोड मान लक्ष्य मान बराबर हुन्छ, हामी यो नोड फिर्ता गर्छौं। अन्यथा, हामीलाई थाहा छ कि लक्ष्य-मूल्यवान नोड या त भित्र हुनेछ बाँकी subtree वा ठिक हालको जडको सबट्री। हामी दिशा (बायाँ वा दायाँ) root.value र लक्ष्य मूल्यको तुलना गरेर निर्णय गर्न सक्छौं। त्यसो भए हामी पनि त्यहि रिकर्सिभ प्रकार्यका साथ कल गर्दछौं मूल as root.left or root.right।

बाइनरी खोज ट्री लीटकोड समाधानमा खोजी गर्नुहोस्

अल्गोरिदम

  1. प्रकार्य सिर्जना गर्नुहोस् SearchBST () लक्ष्य ठेगाना फिर्ता गर्न
  2. If मूल बराबर छ शून्य OR मूल लक्ष्यको जस्तै समान मूल्य छ:
    • मूल फर्काउनुहोस्
  3. यदि root.value लक्ष्य मान भन्दा ठूलो छ:
    1. फिर्ती SearchBST (root.left, val)
  4. फिर्ती SearchBST (root.right, val)
  5. लक्ष्य नोडको प्रिअर्डर traversal प्रिन्ट गर्नुहोस्

बाइनरी खोज ट्री लीटकोड समाधानमा खोजीको कार्यान्वयन

C ++ कार्यक्रम

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

struct BSTNode
{
    int value;
    BSTNode *left , *right;
    BSTNode(int val)
    {
        value = val;
        left = right = NULL;
    }
};

void preorderTraversal(BSTNode* root)
{
    if(root == NULL)
        return;
    cout << root->value << " ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
    return;
}

BSTNode* searchBST(BSTNode* root , int val)
{
    if(root == NULL)
        return root;
    if(val == root->value)
        return root;
    if(val < root->value)
        return searchBST(root->left , val);
    return searchBST(root->right , val);
}

int main()
{
    BSTNode* root = new BSTNode(2);
    root->left = new BSTNode(1);
    root->right = new BSTNode(3);
    root->right->right = new BSTNode(4);
    int val = 3;
    BSTNode* targetNode = searchBST(root , val);
    if(targetNode == NULL)
    {
        cout << "Empty Tree" << '\n';
        return 0;
    }
    preorderTraversal(targetNode);
    return 0;
}

जावा कार्यक्रम

class BSTNode
{
    int value;
    BSTNode left , right;
    BSTNode(int val)
    {
        value = val;
        left = right = null;
    }
}

class search_in_BST
{
    public static void main(String args[])
    {
        BSTNode root = new BSTNode(2);
        root.left = new BSTNode(1);
        root.right = new BSTNode(3);
        root.right.right = new BSTNode(4);
        int val = 3;
        BSTNode targetNode = searchBST(root , val);
        if(targetNode == null)
        {
            System.out.println("Empty Tree");
            System.exit(0);
        }
        preorderTraversal(targetNode);
    }

    static BSTNode searchBST(BSTNode root , int val)
    {
        if(root == null)
            return root;
        if(val == root.value)
            return root;
        if(val < root.value)
            return searchBST(root.left , val);
        return searchBST(root.right , val);
    }

    static void preorderTraversal(BSTNode root)
    {
        if(root == null)
            return;
        System.out.print(root.value + " ");
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return;
    }
}
3 4

एक बाइनरी खोज ट्री लीटकोड समाधानमा खोजीको जटिलता विश्लेषण

समय जटिलता

O (H), H = logN = औसत मामिलामा BST को उचाइ र O (N), N = BST को आकार सबैभन्दा नराम्रो अवस्थामा। हामी रूखलाई एकपटक सबैभन्दा खराब स्थितिमा ट्रान्सभर्स गर्दछौं जुन हुन्छ जब बीएसटी स्क्यूमा हुन्छ।

ठाउँ जटिलता

ओह) औसत मामिलाहरूमा हामी प्रत्येक नोड ट्रान्सवर्स गर्न रिकर्सिव कलहरू प्रयोग गर्दछौं। O (N) सबैभन्दा नराम्रो अवस्थामा। एउटा महत्त्वपूर्ण नोट केहि कम्पाइलरहरू सक्षम छन् पुच्छर पुनरावृत्ति र ती केसहरूमा अन्तरिक्ष जटिलता हुन्छ O (१).

दृष्टिकोण (Iterative)

माथिको दृष्टिकोणमा समान, हामी बायाँ वा दायाँ उपट्रीमा जम्प गर्न सक्छौं यदि लक्षित मान हालको नोडमा अवस्थित छैन भने, हामी यसलाई पुनरागमन द्वारा गर्न सक्दछौं root = root.left or root = root.right प्रत्येक पुनरावृत्ति मा मूल बन्न सम्म खाली। यदि हामीले पत्ता लगायौं कि कुनै मुल्यमा रुटको मान लक्ष्य मान बराबर छ भने हामी त्यो जरा फिर्ता गर्छौं। अन्यथा, हामी फर्कन्छौं खाली।

अल्गोरिदम

  1. उस्तै प्रकार्य सिर्जना गर्नुहोस् SearchBST () त्यो लक्ष्य नोडको ठेगाना फर्काउँछ
  2. जबकि मूल is छैन खाली:
    • if root.value लक्ष्य मान बराबर हो
      • फिर्ती मूल
    • if root.val is अधिक लक्ष्य मान भन्दा
      • दायाँ सबट्रीमा निम्नको रूपमा सार्नुहोस्: root = root.right
    • अरू
      • बाँया subtree मा सार्नुहोस्: root = root.left
  3. फिर्ती शून्य
  4. लक्ष्य नोडको प्रिअर्डर traversal प्रिन्ट गर्नुहोस्

बाइनरी खोज ट्री लीटकोड समाधानमा खोजीको कार्यान्वयन

C ++ कार्यक्रम

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

struct BSTNode
{
    int value;
    BSTNode *left , *right;
    BSTNode(int val)
    {
        value = val;
        left = right = NULL;
    }
};

void preorderTraversal(BSTNode* root)
{
    if(root == NULL)
        return;
    cout << root->value << " ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
    return;
}

BSTNode* searchBST(BSTNode* root , int val)
{
    while(root != NULL)
    {
        if(root->value == val)
            return root;
        if(root->value > val)
            root = root->left;
        else
            root = root->right;
    }
    return NULL;
}

int main()
{
    BSTNode* root = new BSTNode(2);
    root->left = new BSTNode(1);
    root->right = new BSTNode(3);
    root->right->right = new BSTNode(4);
    int val = 3;
    BSTNode* targetNode = searchBST(root , val);
    if(targetNode == NULL)
    {
        cout << "Empty Tree" << '\n';
        return 0;
    }
    preorderTraversal(targetNode);
    return 0;
}

जावा कार्यक्रम

class BSTNode
{
    int value;
    BSTNode left , right;
    BSTNode(int val)
    {
        value = val;
        left = right = null;
    }
}

class search_in_BST
{
    public static void main(String args[])
    {
        BSTNode root = new BSTNode(2);
        root.left = new BSTNode(1);
        root.right = new BSTNode(3);
        root.right.right = new BSTNode(4);
        int val = 3;
        BSTNode targetNode = searchBST(root , val);
        if(targetNode == null)
        {
            System.out.println("Empty Tree");
            System.exit(0);
        }
        preorderTraversal(targetNode);
    }

    static BSTNode searchBST(BSTNode root , int val)
    {
        while(root != null)
        {
            if(root.value == val)
                return root;
            if(root.value > val)
                root = root.left;
            else
                root = root.right;
        }
        return null;
    }

    static void preorderTraversal(BSTNode root)
    {
        if(root == null)
            return;
        System.out.print(root.value + " ");
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return;
    }
}
3 4

एक बाइनरी खोज ट्री लीटकोड समाधानमा खोजीको जटिलता विश्लेषण

समय जटिलता

O (H = logN) औसत अवस्थामा र O (N) खराब अवस्थामा (माथी BST), माथिको दृष्टिकोण जस्तै।

ठाउँ जटिलता

O (१) किनकि हामी केवल स्थिर मेमोरी स्पेस मात्र प्रयोग गर्छौं।