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


कठिनाई तह मध्यम
बारम्बार सोधिन्छ अमेजन एप्पल Atlassian फेसबुक गुगल माइक्रोसफ्ट
बाइनरी खोज रूख

यस समस्यामा हामीलाई a को मूल नोड दिइन्छ बाइनरी खोज रूख पूर्णांक मानहरू र नोडको एक पूर्णांक मान समावेश गर्दछ जुन हामीले बाइनरी खोज रूखमा थप्नु पर्छ र यसको संरचना फिर्ता गर्नुपर्दछ। BST मा एलिमेन्ट घुसाएपछि, हामीले यसको ईन्डर ट्रभर्सल प्रिन्ट गर्नुपर्नेछ।

उदाहरणका

Binary Search Tree:
 
    7
 
  /     \

3         10

        /

      8
Integer Value = 11
3 7 8 10 11
Binary Search Tree:
           5

         /

       4

     /

   3
Integer Value = 2
2 3 4 5

स्पष्टीकरण

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

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

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

हाम्रो बाइनरी खोज ट्रीमा कुनै नोड कहाँ राख्नुपर्नेछ भनेर निर्णय गर्न, हामीले मूलबाट सम्बन्धित नोडको लागि मार्ग सेट गर्नुपर्नेछ जसको बायाँ / दायाँ बच्चा दिइएको नोड हुनेछ।

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

अल्गोरिदम

  1. प्रकार्य सिर्जना गर्नुहोस् insertIntoBST () जुन ठेगाना फिर्ता गर्दछ मूल दिएका सम्मिलित पछि BST को नोड
  2. insertIntoBST () दुई प्यारामिटरहरू छन्: मूल रूखको र मूल्य घुसाउनु पर्ने नोडको
  3. प्रकार्यले निम्न कार्य गर्दछ:
    • If मूल is खाली, दिइएका मान जस्तै समान मानको साथ नयाँ रूख नोड फर्काउनुहोस्
    • यदि दिइएको मान छ भने अधिक को मान भन्दा मूल नोड, त्यसपछि समान समस्यालाई दाँया सबट्रीमा कल गर्नुहोस् र रूट फिर्ता गर्नुहोस्
      • root.right = insertIntoBST (मूल-> सहि, मान)
      • फिर्ती मूल
    • बाँकी subtree मा अन्य खोज निम्नको रूपमा:
      • root.left= insertIntoBST (root.left, मान)
      • फिर्ती मूल
  4. बाइनरी खोज ट्रीको inverse traversal प्रिन्ट गर्नुहोस्

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

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

#include <bits/stdc++.h>
using namespace std;
struct BSTNode
{
    int value;
    BSTNode *left , *right;
    BSTNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};

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


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

int main()
{
    BSTNode* root = new BSTNode(7);
    root->left = new BSTNode(3);
    root->right = new BSTNode(10);
    root->right->left = new BSTNode(8);
    int val = 11;
    root = insertIntoBST(root , val);
    inorderTraversal(root);
    return 0;
}

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

class BSTNode
{
    int value;
    BSTNode left , right;

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

class insert_into_BST
{
    public static void main(String args[])
    {
        BSTNode root = new BSTNode(7);
        root.left = new BSTNode(3);
        root.right = new BSTNode(10);
        root.right.left = new BSTNode(8);
        int val = 11;
        root = insertIntoBST(root , val);
        inorderTraversal(root);
    }

    static BSTNode insertIntoBST(BSTNode root , int val)
    {
        if(root == null)
            return new BSTNode(val);
        if(val > root.value)
        {
            root.right = insertIntoBST(root.right , val);
            return root;
        }
        root.left = insertIntoBST(root.left , val);
        return root;
    }

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

3 7 8 10 11

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

समय जटिलता

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

ठाउँ जटिलता

ओह) औसत अवस्थामा। O (N) सबैभन्दा खराब अवस्थामा। स्पेस जटिलता को केस यहाँ समय जटिलता को रूप मा समान छ किनकि यो हामी गर्छन रिकर्सिभ कलहरु को संख्या मा निर्भर गर्दछ।

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

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

अल्गोरिदम

  1. हामीसँग फेरि एक छ insertIntoBST () माथिको जस्तै उद्देश्यको लागि
  2. यो भने मूल NULL हो
    1. नयाँ नोडलाई दिइएको मान जस्तै मानको साथ फर्काउनुहोस्
  3. मूलको एक प्रतिलिपि सिर्जना गर्नुहोस्, भन्नुहोस् डमी BST को सामग्रीलाई हेरफेर गर्न
  4. जबकि डमी is छैन खाली
    1. यदि दिइएको मान भन्दा बढि छ root.val
      1. If root.right NULL हो
        1. root.right = नयाँ नोड दिइएको मानको साथ
        2. फिर्ती मूल
      2. अर्को, सेट
        1. मूल = root.right, दाँया सबट्रीमा जम्प गर्न
    2. अन्यथा यदि मान भन्दा कम वा बराबर छ root.val
      1. यदि root.left NULL छ
        1. root.left = नयाँ नोड दिइएको मानको साथ
        2. फिर्ती मूल
      2. अर्को, सेट
        1. मूल = root.left, बाँया subtree मा जम्प गर्न
  5. BST को Inorder traversal प्रिन्ट गर्नुहोस्

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

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

#include <bits/stdc++.h>
using namespace std;
struct BSTNode
{
    int value;
    BSTNode *left , *right;
    BSTNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};

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

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

int main()
{
    BSTNode* root = new BSTNode(7);
    root->left = new BSTNode(3);
    root->right = new BSTNode(10);
    root->right->left = new BSTNode(8);
    int val = 11;
    root = insertIntoBST(root , val);
    inorderTraversal(root);
    return 0;
}

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

class BSTNode
{
    int value;
    BSTNode left , right;

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

class insert_into_BST
{
    public static void main(String args[])
    {
        BSTNode root = new BSTNode(7);
        root.left = new BSTNode(3);
        root.right = new BSTNode(10);
        root.right.left = new BSTNode(8);
        int val = 11;
        root = insertIntoBST(root , val);
        inorderTraversal(root);
    }

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

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

3 7 8 10 11

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

समय जटिलता

ओह) = BST को उचाई = लग एन (जहाँ N = BST मा नोडहरूको संख्या) औसत केसहरूमा। तर O (N) सबैभन्दा खराब स्थितिमा जब रूख काटिएको छ। फेरि, समय जटिलता हामी गन्तव्यमा पुग्न पुनरावृत्तिहरूको संख्यामा निर्भर हुन्छ जुन दिइएको नोड सम्मिलित हुनुपर्दछ र यो रूख स्ट्रक्चरमा निर्भर गर्दछ।

ठाउँ जटिलता

O (१)। सबैभन्दा नराम्रो अवस्थामा पनि हामी केवल भ्यारीएबलका लागि स्थिर स्थान प्रयोग गर्दछौं।