બાઈનરી ટ્રી લીટકોડ સોલ્યુશનની ન્યૂનતમ thંડાઈ


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એમેઝોન સફરજન ફેસબુક
દ્વિસંગી વૃક્ષ બ્રેડથ ફર્સ્ટ સર્ચ Thંડાઈ પ્રથમ શોધ

આ સમસ્યામાં આપણને આપેલા મૂળમાં કોઈપણ પાંદડા સુધીના ટૂંકા માર્ગની લંબાઈ શોધવાની જરૂર છે દ્વિસંગી વૃક્ષ. નોંધ લો કે અહીં “પાથની લંબાઈ” નો અર્થ મૂળ નોડથી પર્ણ નોડ સુધીના ગાંઠોની સંખ્યા છે. આ લંબાઈને દ્વિસંગી વૃક્ષની ન્યૂનતમ thંડાઈ કહેવામાં આવે છે.

ઉદાહરણ

ઇનપુટ

બાઈનરી ટ્રી લીટકોડ સોલ્યુશનની ન્યૂનતમ thંડાઈ

 

 

 

 

 

 

 

2

સમજૂતી

ટૂંકી માર્ગ: 2 -> 1 , જે લંબાઈ 2 ની છે

ઇનપુટ

 

 

 

 

 

 

 

3

સમજૂતી

ટૂંકમાં પાથ છે: 1 -> 2 -> 3, લંબાઈ 3

અભિગમ (પુનરાવર્તિત)

આ સમસ્યા બાઈનરી ઝાડની heightંચાઇ શોધવા જેવી રચનાત્મક સમાન છે પરંતુ આ કિસ્સામાં, આપણે ઝાડના મૂળ અને કોઈપણ પાંદડા વચ્ચે લઘુત્તમ heightંચાઇ / depthંડાઈ શોધવાની જરૂર છે. આપણે રુટની મદદથી ડાબી અને જમણી સબટ્રીઝની ન્યૂનતમ depંડાઈ મેળવી શકીએ છીએ Thંડાઈ પ્રથમ શોધ (ડીએફએસ) અને પછી બે depંડાણોમાંથી ઓછામાં ઓછું પરત કરો. જ્યારે આપણે નોડની ડાબી અને જમણી પેટામાંથી કોઈપણ હોય ત્યારે કેટલાક કેસો ધ્યાનમાં લેવાની જરૂર છે NULL. જો ડાબી સબટ્રી છે નલ, તે બરાબર heightંચાઇ પરત કરશે પરંતુ આ સબટ્રીમાં અમને કોઈ પાંદડું મળ્યું નથી, તેથી આ ખોટો જવાબ હશે. તેથી, જ્યારે આપણે નોડ ઉપર બોલાવ્યું હોય ત્યારે જ આપણે રિકર્સીવ ફંક્શનને ક toલ કરવાની જરૂર છે નથી નલ.

અલ્ગોરિધમ

  1. ફંકશન બનાવો મિનિટડેપ્થ () પસાર મૂળની લઘુત્તમ depthંડાઈ પરત કરવા માટે
  2. જો મૂળ છે NULL, પાછા 0
  3. કિસ્સામાં બંને બાકી અને અધિકાર સબટ્રીઝ છે NULL, વળતર 1
  4. જો ડાબી સબટ્રી છે NULL, પાછા 1 + મિનિટડેપ્થ (મૂળ-> અધિકાર)
  5. બાકી જો કેસ યોગ્ય સબટ્રી છે NULL, પાછા 1 + મિનિટડેપ્થ (રુટ-> ડાબી)
  6. વળતર 1 + લઘુત્તમ (minDepth(મૂળ-> ડાબી), minDepth(મૂળ-> અધિકાર))

બાઈનરી ટ્રી લીટકોડ સોલ્યુશનની ન્યૂનતમ Depંડાઈનો અમલ

સી ++ પ્રોગ્રામ

#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

બાઈનરી ટ્રી લીટકોડ સોલ્યુશનની ન્યૂનતમ thંડાઈનું જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન), કારણ કે આપણે એકદમ ખરાબ કિસ્સામાં પણ એકવાર આખા વૃક્ષને વટાવીએ છીએ.

જગ્યાની જટિલતા

ઓ (એન) જ્યારે બાઈનરી ટ્રી સ્કીંગ કરવામાં આવે છે, ત્યારે રિકરિવ સ્ટેક ફ્રેમ્સ O (N) જગ્યા સુધીનો વપરાશ કરી શકે છે.

અભિગમ (Iterative)

આપણે વાપરી શકીએ છીએ બ્રેડથ-ફર્સ્ટ સર્ચ (બી.એફ.એસ.) પ્રથમ નોડ શોધવા માટે જે એક પાંદડું છે અને તેની depthંડાઈને મૂળમાંથી પાછું આપે છે. રુટ નોડથી ગાંઠોની જોડી અને તેની thsંડાણો સંગ્રહિત કરવા માટે અમે કતારનો ઉપયોગ કરી શકીએ છીએ. જેમ કે આપણને એક નોડ મળે છે જે એક પાંદડું છે, અમે તેની depthંડાઈ પરત કરીએ છીએ.

અલ્ગોરિધમ

  1. જો રુટ છે NULL, પાછા 0
  2. ટ્રી નોડ્સ અને પૂર્ણાંકોની જોડની કતાર શરૂ કરો
  3. રુટ નોડને તેની depthંડાઈ સાથે કતારમાં દબાણ કરો 1
  4. જ્યારે કતાર ખાલી નથી:
    • આગળની કતાર તત્વની depthંડાઈ અને નોડ સરનામું પ્રાપ્ત કરો
    • કતારમાંથી એક આઇટમ પ Popપ કરો
    • જો આગળનો નોડ છે NULL, તેની depthંડાઈ પરત
    • દબાણ કરો બાકી અને અધિકાર ઝાડ પર ગાંઠો જો તેઓ હોય નથી નલ
  5. રીટર્ન -1 પ્રોગ્રામના સિન્ટેક્સને જાળવવા માટે, જેમ કે ફંક્શન પૂર્ણાંક આપે છે

બાઈનરી ટ્રી લીટકોડ સોલ્યુશનની ન્યૂનતમ Depંડાઈનો અમલ

સી ++ પ્રોગ્રામ

#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

બાઈનરી ટ્રી લીટકોડ સોલ્યુશનની ન્યૂનતમ thંડાઈનું જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન), જેમ આપણે ફરી એકવાર આખા વૃક્ષને વટાવીએ છીએ.

જગ્યાની જટિલતા

ઓ (એન), જેમ કે આપણે દરેક નોડની વિગતો સ્ટોર કરવા માટે કતારનો ઉપયોગ કરીએ છીએ.