बायनरी ट्री लीटकोड सोल्यूशनची किमान खोली


अडचण पातळी सोपे
वारंवार विचारले ऍमेझॉन सफरचंद फेसबुक
बायनरी ट्री रुंदी प्रथम शोध खोली प्रथम शोध

या समस्येमध्ये, आपल्याला दिलेल्या मुळापासून कोणत्याही पानापर्यंत सर्वात लहान मार्गाची लांबी शोधणे आवश्यक आहे बायनरी ट्री. लक्षात घ्या की येथे असलेल्या "मार्गाची लांबी" चा अर्थ मूळ नोड ते लीफ नोडपर्यंत असलेल्या नोड्सची संख्या आहे. या लांबीला ए बायनरी ट्रीची किमान खोली म्हणतात.

उदाहरण

इनपुट

बायनरी ट्री लीटकोड सोल्यूशनची किमान खोली

 

 

 

 

 

 

 

2

स्पष्टीकरण

सर्वात छोटा मार्ग आहे: 2 -> 1 2 ची लांबी आहे

इनपुट

 

 

 

 

 

 

 

3

स्पष्टीकरण

सर्वात छोटा मार्ग आहे: 1 -> 2 -> 3लांबी 3

दृष्टीकोन (रिकर्सीव्ह)

ही समस्या बायनरी झाडाची उंची शोधण्याइतकीच रचनात्मकदृष्ट्या आहे परंतु या प्रकरणात, आम्हाला झाडाच्या मूळ आणि कोणत्याही पानांमधील किमान उंची / खोली शोधण्याची आवश्यकता आहे. आम्ही रूटच्या डावी आणि उजवीकडील उपशीर्षांची किमान खोली शोधून काढू शकतो खोली प्रथम शोध (डीएफएस) आणि नंतर दोन खोलींमधील किमान परत करा. जेव्हा नोडच्या डाव्या आणि उजव्या उपखंडांपैकी एक असेल तेव्हा आम्हाला काही प्रकरणांचा विचार करणे आवश्यक आहे निरर्थक. डावे सबट्री असल्यास निरर्थक, तेवढी उंची परत येईल परंतु आपल्याला या सबट्रीमध्ये कोणतेही पान सापडले नाही, म्हणून हे हे चुकीचे उत्तर असेल. म्हणूनच, आपल्याला फक्त रिकर्सिव्ह फंक्शन कॉल करणे आवश्यक आहे जेव्हा ते ज्यावर कॉल केले जाते तेव्हा नाही निरर्थक.

अल्गोरिदम

  1. एक फंक्शन तयार करा minDepth () उत्तीर्ण मुळाची किमान खोली परत करणे
  2. जर मूळ असेल निरर्थक, परत 0
  3. दोन्ही बाबतीत बाकी आणि योग्य उपट्री आहेत निरर्थक, परत 1
  4. डावे सबट्री असल्यास निरर्थक, परत 1 + मिनिटापर्यंत (रूट-> उजवीकडे)
  5. अन्यथा जर योग्य सबट्री असेल तर निरर्थक, परत 1 + minDepth (मूळ-> डावीकडे)
  6. 1 + किमान परत करा (minDepth(मूळ-> डावीकडे), minDepth(मूळ-> उजवीकडे))

बायनरी ट्री लीटकोड सोल्यूशनच्या किमान खोलीची अंमलबजावणी

सी ++ प्रोग्राम

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

int minDepth(treeNode* root)
{
    if(root == NULL)
        return 0;
    if(root->left == NULL && root->right == NULL)
        return 1;
    if(root->left == NULL)
        return 1 + minDepth(root->right);
    if(root->right == NULL)
        return 1 + minDepth(root->left);
    return 1 + min(minDepth(root->left) , minDepth(root->right));
}

int main()
{
    treeNode* root = new treeNode(2);
    root->left = new treeNode(1);
    root->right = new treeNode(3);
    root->right->left = new treeNode(4);
    root->right->right = new treeNode(5);
    cout << minDepth(root) << '\n';
}

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

import java.util.*;

class treeNode
{
    int value;
    treeNode left, right;
    public treeNode(int x)
    {
        value = x;
        left = right = null;
    }
}

class Pair
{
    treeNode key;
    int value;

    Pair(treeNode root , int val)
    {
        key = root;
        value = val;
    }
}

class Minimum_Depth_Of_A_Binary_Tree
{
    public static void main(String args[])
    {
        treeNode root = new treeNode(2);
        root.left = new treeNode(1);
        root.right = new treeNode(3);
        root.right.left = new treeNode(4);
        root.right.right = new treeNode(5);
        System.out.println(minDepth(root));
    }

    static int minDepth(treeNode root)
    {
        if(root == null)
            return 0;
        if(root.left == null && root.right == null)
            return 1;
        if(root.left == null)
            return 1 + minDepth(root.right);
        if(root.right == null)
            return 1 + minDepth(root.left);
        return 1 + Math.min(minDepth(root.left) , minDepth(root.right));

    }
}
2

बायनरी ट्री लीटकोड सोल्यूशनच्या किमान खोलीची जटिलता विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन), जसे की आम्ही अगदी वाईट परिस्थितीत एकदाच संपूर्ण झाड ओलांडले.

जागेची जटिलता

ओ (एन) जेव्हा बायनरी ट्री स्क्यू केली जाते तेव्हा रिकर्सिव्ह स्टॅक फ्रेम्स ओ (एन) पर्यंत जागा घेतात.

दृष्टीकोन (Iterative)

आम्ही वापरू शकतो ब्रेडथ-फर्स्ट सर्च (बीएफएस) एक पान असलेला पहिला नोड शोधण्यासाठी आणि त्याची खोली मूळपासून परत करा. आम्ही रूट नोड वरुन नोड्सची जोड आणि त्यांची खोली साठवण्यासाठी रांग वापरू शकतो. आम्हाला एक पाने आहे जे एक पाने आहे, आम्ही त्याची खोली परत करतो.

अल्गोरिदम

  1. जर मूळ असेल निरर्थक, परत 0
  2. ट्री नोड्स आणि पूर्णांकांच्या जोडीची रांग सुरू करा
  3. त्याच्या खोलीसह रांगावर रूट नोड पुश करा 1
  4. रांग रिक्त नसतानाही:
    • पुढील रांगेच्या घटकाची खोली आणि नोड पत्ता पुनर्प्राप्त करा
    • रांगेतून आयटम पॉप करा
    • समोरचा नोड असल्यास निरर्थक, त्याची खोली परत करा
    • ढकलणे बाकी आणि योग्य झाडावर नोड्स असल्यास नाही निरर्थक
  5. परत -1 प्रोग्रामचा सिंटॅक्स देखरेख ठेवण्यासाठी फंक्शन पूर्णांक मिळवते

बायनरी ट्री लीटकोड सोल्यूशनच्या किमान खोलीची अंमलबजावणी

सी ++ प्रोग्राम

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

int minDepth(treeNode* root)
{
    if(root == NULL)
        return 0;
    queue < pair <treeNode* , int> > q;
    q.push({root , 1});

    treeNode* frontNode;
    int depth;

    while(!q.empty())
    {
        frontNode = q.front().first;
        depth = q.front().second;
        q.pop();

        if(frontNode->left == NULL && frontNode->right == NULL)
            return depth;

        if(frontNode->left != NULL)
            q.push({frontNode->left , depth + 1});

        if(frontNode->right != NULL)
            q.push({frontNode->right , depth + 1});
    }
    return -1;
}

int main()
{
    treeNode* root = new treeNode(2);
    root->left = new treeNode(1);
    root->right = new treeNode(3);
    root->right->left = new treeNode(4);
    root->right->right = new treeNode(5);
    cout << minDepth(root) << '\n';
}


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

import java.util.*;

class treeNode
{
    int value;
    treeNode left, right;
    public treeNode(int x)
    {
        value = x;
        left = right = null;
    }
}

class Pair
{
    treeNode key;
    int value;

    Pair(treeNode root , int val)
    {
        key = root;
        value = val;
    }
}

class Minimum_Depth_Of_A_Binary_Tree
{
    public static void main(String args[])
    {
        treeNode root = new treeNode(2);
        root.left = new treeNode(1);
        root.right = new treeNode(3);
        root.right.left = new treeNode(4);
        root.right.right = new treeNode(5);
        System.out.println(minDepth(root));
    }

    static int minDepth(treeNode root)
    {
        if(root == null)
            return 0;
        LinkedList <Pair> q = new LinkedList<>();
        q.add(new Pair(root , 1));

        treeNode frontNode;
        int depth;

        while(q.size() > 0)
        {
            frontNode = q.peek().key;
            depth = q.peek().value;

            q.remove();

            if(frontNode.left == null && frontNode.right == null)
                return depth;

            if(frontNode.left != null)
                q.add(new Pair(frontNode.left , depth + 1));

            if(frontNode.right != null)
                q.add(new Pair(frontNode.right , depth + 1));
        }
        return -1;
    }
}
2

बायनरी ट्री लीटकोड सोल्यूशनच्या किमान खोलीची जटिलता विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन), जसे आम्ही पुन्हा एकदा संपूर्ण झाड ओलांडत आहोत.

जागेची जटिलता

ओ (एन), जसे आम्ही प्रत्येक नोडचा तपशील संग्रहित करण्यासाठी रांग वापरतो.