એન-એરી ટ્રી લીટકોડ સોલ્યુશનની મહત્તમ thંડાઈ


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

આ સમસ્યામાં, અમને એક આપવામાં આવે છે એન-એરી ટ્રી, એટલે કે, એક વૃક્ષ જે ગાંઠોને 2 થી વધુ બાળકોની મંજૂરી આપે છે. આપણે ઝાડના મૂળથી દૂર પર્ણની theંડાઈ શોધવાની જરૂર છે. તેને મહત્તમ depthંડાઈ કહેવામાં આવે છે. નોંધ કરો કે પાથની depthંડાઈ એ તેના પર ગાંઠોની સંખ્યા છે.

ઉદાહરણ

       2

  /    |    \

3      4      6

                \
           
                  9
3

સમજૂતી: મૂલ્ય 9 સાથેનું પાન મૂળથી ખૂબ દૂર છે અને તેની depthંડાઈ છે 3. તેથી, આપણે 3 છાપીશું.

      2
  
  /      \

3           6   

        /   |   \

      4     7     9
3

સમજૂતી: મૂલ્ય 4,7 અને 9 ના પાંદડા મૂળથી સૌથી દૂર છે અને તેની depthંડાઈ છે 3. તેથી, આપણે 3 છાપીશું.

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

દ્વિસંગી વૃક્ષની મહત્તમ depthંડાઈની ગણતરી કોઈપણ નોડના ડાબી અને જમણી બાળકો પર રિકર્સીવ ફંક્શનને બોલાવીને કરવામાં આવે છે. એ જ રીતે, એન-એરી ટ્રીના કિસ્સામાં, આપણે કોઈપણ નોડના બધા બાળકો પર રિકર્સીવ ફંક્શનને બોલાવીને મહત્તમ depthંડાઈની ગણતરી કરી શકીએ છીએ. આ અભિગમ પુનરાવર્તિત છે અને તેને ફક્ત ઝાડનો એક જ પાસ જરૂરી છે.

એન-એરી ટ્રી લીટકોડ સોલ્યુશનની મહત્તમ thંડાઈ

અલ્ગોરિધમ

  1. ફંકશન બનાવો મહત્તમડેપ્થ () જેની ઝાડની મહત્તમ depthંડાઈ પરત આપવી રુટ તે પસાર થાય છે
  2. If રુટ નલ છે:
    • 0 પરત કરો
  3. ચલ શરૂ કરો મહત્તમ ડેપ્થ એન-એરી વૃક્ષની મહત્તમ depthંડાઈ સ્ટોર કરવા
  4. બધા માટે બાળક વર્તમાન મૂળની બાળકોની સૂચિમાં:
    • સમૂહ મહત્તમડેપ્થ = મેક્સમ (મેક્સડેપ્થ (રૂટ.લેફ્ટ), મેક્સડેપ્થ (રૂટ.રાઇટ))
  5. વળતર મહત્તમ ડેપ્થ + 1

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

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

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

struct Node
{
    int value;
    vector <Node*> children;

    Node(int val)
    {
        value = val;
        children = {};
    }

    Node(int val , vector <Node*> childList)
    {
        value = val;
        children = childList;
    }
};

int maxDepth(Node* root)
{
    if(root == NULL)
        return 0;
    int maximumDepth = 0;
    for(Node* &child : root->children)
        maximumDepth = max(maximumDepth , maxDepth(child));
    return maximumDepth + 1;
}

int main()
{
    Node* root = new Node(2);
    root->children = {new Node(3) , new Node(4) , new Node(5)};
    root->children[2]->children = {new Node(9)};
    cout << maxDepth(root) << '\n';
    return 0;
}

જાવા પ્રોગ્રામ

import java.lang.Math;

class Node
{
    int value;
    Node[] children;

    Node(int val)
    {
        value = val;
        children = new Node[]{};
    }

    Node(int val , Node[] childList)
    {
        value = val;
        children = childList;
    }
};

class maximum_depth
{
    public static void main(String args[])
    {
        Node root = new Node(2);
        Node[] a = {new Node(3) , new Node(4) , new Node(5)};
        root.children = a;
        Node[] b = {new Node(9)};
        root.children[2].children = b;
        System.out.println(maxDepth(root));
    }

    static int maxDepth(Node root)
    {
        if(root == null)
            return 0;
        int maximumDepth = 0;
        for(int i = 0 ; i < root.children.length ; i++)
            maximumDepth = Math.max(maximumDepth , maxDepth(root.children[i]));
        return maximumDepth + 1;
    }
}
3

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

સમય જટિલતા

ઓ (એન), એન એન-એરી ઝાડનું કદ જ્યારે આપણે આખા વૃક્ષને એકવાર પસાર કરીશું.

અવકાશ જટિલતા

ઓ (એન) આપણે રિકરિવ કiveલ્સ માટે મેમરીમાં સ્ટેક ફ્રેમ્સ સ્ટોર કરીએ છીએ.

અભિગમ (આઇટરેટિવ)

આપણે ઉપરોક્ત પ્રક્રિયાને પુનરાવર્તિત રૂપે સ્ટેક અથવા કતારનો ઉપયોગ કરીને ગાંઠો અને તેમની thsંડાણોને મૂળમાંથી સંગ્રહિત કરી શકીએ છીએ. મહત્તમ depthંડાઈ આ પ્રક્રિયામાંથી પ્રાપ્ત થયેલ તમામ મૂળની મહત્તમ thsંડાઈ હશે. અમે આ હેતુ માટે કતારનો ઉપયોગ કરીએ છીએ અને ઝાડના તમામ તત્વોને તેની મૂળમાંથી thsંડાણો સાથે કતારમાં દબાણ કરીએ છીએ. અમે દરેક નોડની depthંડાઈની મહત્તમ depthંડાઈ સાથે તુલના કરીએ છીએ અને તેને અપડેટ કરીએ છીએ.

અલ્ગોરિધમ

  1. ફંકશન બનાવો મહત્તમડેપ્થ () ઉપરના અભિગમમાં ચર્ચા કરેલી સમાન
  2. If રુટ is નલ:
    • 0 પરત કરો
  3. પ્રારંભ મહત્તમ ડેપ્થ અમારા પરિણામ સંગ્રહવા માટે
  4. કતાર શરૂ કરો તત્વો જેમાં ઝાડ ગાંઠો અને તેમની thsંડાણો શામેલ છે
  5. દબાણ કરો રુટ અને તેની depthંડાઈ કતારમાં 1 જેટલી છે
  6. જ્યારે તત્વો ખાલી નથી:
    • આગળનો નોડ અને તેની heightંચાઈને મેળવો ફ્રન્ટનોડ અને ફ્રન્ટનોડડેપ્થ
    • કતારમાંથી એક આઇટમ પ Popપ કરો
    • If ફ્રન્ટનોડડેપ્થ is વધારે કરતાં મહત્તમ ડેપ્થ
      1. અપડેટ મહત્તમડેપ્થ = ફ્રન્ટનોડડેપ્થ
    • If ફ્રન્ટનોડ is નલ નથી:
      1. તેના તમામ બાળકોને તેમની depંડાણો સાથે કતારમાં દબાણ કરો ફ્રન્ટનોડડેપ્થ + 1
  7. વળતર મહત્તમ ડેપ્થ
  8. પરિણામ છાપો

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

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

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

struct Node
{
    int value;
    vector <Node*> children;

    Node(int val)
    {
        value = val;
        children = {};
    }

    Node(int val , vector <Node*> childList)
    {
        value = val;
        children = childList;
    }
};

int maxDepth(Node* root)
{
    if(root == NULL)
        return 0;
    int maximumDepth = 0 , frontNodeDepth;

    queue <pair <Node* , int> > elements;
    elements.push({root , 1});
    Node* frontNode;
    while(!elements.empty())
    {
        frontNode = elements.front().first;
        frontNodeDepth = elements.front().second;
        elements.pop();
        if(frontNodeDepth > maximumDepth)
            maximumDepth = frontNodeDepth;

        if(frontNode != NULL)
        {
            for(Node* &child : frontNode->children)
                elements.push({child , frontNodeDepth + 1});
        }
    }

    return maximumDepth;
}

int main()
{
    Node* root = new Node(2);
    root->children = {new Node(3) , new Node(4) , new Node(5)};
    root->children[2]->children = {new Node(9)};
    cout << maxDepth(root) << '\n';
    return 0;
}

જાવા પ્રોગ્રામ

import java.lang.Math;
import java.util.*;

class Node
{
    int value;
    Node[] children;

    Node(int val)
    {
        value = val;
        children = new Node[]{};
    }

    Node(int val , Node[] childList)
    {
        value = val;
        children = childList;
    }
};

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

class maximum_depth
{
    public static void main(String args[])
    {
        Node root = new Node(2);
        Node[] a = {new Node(3) , new Node(4) , new Node(5)};
        root.children = a;
        Node[] b = {new Node(9)};
        root.children[2].children = b;
        System.out.println(maxDepth(root));
    }

    static int maxDepth(Node root)
    {
        if(root == null)
            return 0;
        LinkedList <Pair> elements = new LinkedList <>();
        elements.add(new Pair(root , 1));
        Node frontNode;
        int maximumDepth = 0 , frontNodeDepth;

        while(elements.size() > 0)
        {
            frontNode = elements.peek().key;
            frontNodeDepth = elements.peek().value;
            elements.remove();
            if(frontNodeDepth > maximumDepth)
                maximumDepth = frontNodeDepth;

            if(frontNode != null)
            {
                for(int i = 0 ; i < frontNode.children.length ; i++)
                    elements.add(new Pair(frontNode.children[i] , frontNodeDepth + 1));
            }
        }
        return maximumDepth;
    }
}
3

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

સમય જટિલતા

ઓ (એન) અમે ફરીથી આખા વૃક્ષને વટાવીએ છીએ. એન = ઝાડનું કદ

અવકાશ જટિલતા

ઓ (એન) જેમ કે આપણે વૃક્ષમાં બધા ગાંઠો તેમની thsંડાઈ સાથે સંગ્રહિત કરવા માટે કતારનો ઉપયોગ કરીએ છીએ.