ఎన్-ఆరీ ట్రీ లీట్‌కోడ్ సొల్యూషన్ యొక్క గరిష్ట లోతు


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది అమెజాన్ గూగుల్ మైక్రోసాఫ్ట్
వెడల్పు మొదటి శోధన లోతు మొదటి శోధన ఎన్-ఆరి-చెట్టు

ఈ సమస్యలో, మాకు ఒక ఇవ్వబడుతుంది ఎన్-ఆరి చెట్టు, అనగా, నోడ్స్‌కు 2 కంటే ఎక్కువ పిల్లలు ఉండటానికి అనుమతించే చెట్టు. చెట్టు యొక్క మూల నుండి దూరంగా ఉన్న ఆకు యొక్క లోతును మనం కనుగొనాలి. దీన్ని గరిష్ట లోతు అంటారు. ఒక మార్గం యొక్క లోతు దానిపై ఉన్న నోడ్‌ల సంఖ్య అని గమనించండి.

ఉదాహరణ

       2

  /    |    \

3      4      6

                \
           
                  9
3

వివరణ: విలువ 9 ఉన్న ఆకు రూట్ నుండి చాలా దూరంలో ఉంటుంది మరియు దాని లోతు ఉంటుంది 3. కాబట్టి, మేము 3 ను ప్రింట్ చేస్తాము.

      2
  
  /      \

3           6   

        /   |   \

      4     7     9
3

వివరణ: 4,7 మరియు 9 విలువ కలిగిన ఆకులు మూలం నుండి దూరంగా ఉంటాయి మరియు వాటి లోతు ఉంటుంది 3. కాబట్టి, మేము 3 ను ప్రింట్ చేస్తాము.

అప్రోచ్ (రికర్సివ్)

ఏదైనా నోడ్ యొక్క ఎడమ మరియు కుడి పిల్లలపై పునరావృత ఫంక్షన్‌ను పిలవడం ద్వారా బైనరీ చెట్టు యొక్క గరిష్ట లోతు లెక్కించబడుతుంది. అదేవిధంగా, N-ary చెట్టు విషయంలో, ఏదైనా నోడ్‌లోని పిల్లలందరిపై పునరావృత ఫంక్షన్‌ను పిలవడం ద్వారా గరిష్ట లోతును లెక్కించవచ్చు. ఈ విధానం పునరావృతమవుతుంది మరియు చెట్టు యొక్క ఒకే పాస్ మాత్రమే అవసరం.

ఎన్-ఆరీ ట్రీ లీట్‌కోడ్ సొల్యూషన్ యొక్క గరిష్ట లోతు

అల్గారిథం

  1. ఒక ఫంక్షన్ సృష్టించండి maxDepth () చెట్టు యొక్క గరిష్ట లోతును తిరిగి ఇవ్వడానికి రూట్ దానికి పంపబడుతుంది
  2. If రూట్ శూన్యమైనది:
    • తిరిగి 0
  3. వేరియబుల్ ప్రారంభించండి గరిష్ట లోతు N-ary చెట్టు యొక్క గరిష్ట లోతును నిల్వ చేయడానికి
  4. ప్రతి కోసం పిల్లల ప్రస్తుత మూలం యొక్క పిల్లల జాబితాలో:
    • సెట్ maxDepth = max (maxDepth (root.left), maxDepth (root.right))
  5. తిరిగి గరిష్ట డెప్త్ + 1

ఎన్-ఆరీ ట్రీ లీట్‌కోడ్ సొల్యూషన్ యొక్క గరిష్ట లోతు అమలు

సి ++ ప్రోగ్రామ్

#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

ఎన్-ఆరీ ట్రీ లీట్‌కోడ్ సొల్యూషన్ యొక్క గరిష్ట లోతు యొక్క సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

ఓ (ఎన్), ఎన్ = మొత్తం చెట్టును ఒకసారి ప్రయాణించేటప్పుడు N- ఆరీ చెట్టు యొక్క పరిమాణం.

అంతరిక్ష సంక్లిష్టత

పై) పునరావృత కాల్‌ల కోసం మేము స్టాక్ ఫ్రేమ్‌లను మెమరీలో నిల్వ చేస్తున్నప్పుడు.

అప్రోచ్ (పునరుక్తి)

నోడ్లను మరియు వాటి లోతును రూట్ నుండి నిల్వ చేయడానికి స్టాక్ లేదా క్యూను ఉపయోగించడం ద్వారా పై ప్రక్రియను మనం పునరుక్తిగా చేయవచ్చు. ఈ ప్రక్రియ నుండి పొందిన అన్ని మూలాల లోతు యొక్క గరిష్ట లోతు ఉంటుంది. మేము ఈ ప్రయోజనం కోసం ఒక క్యూను ఉపయోగిస్తాము మరియు చెట్టు యొక్క అన్ని మూలకాలను వాటి లోతుతో పాటు క్యూలోకి నెట్టివేస్తాము. మేము ప్రతి నోడ్ యొక్క లోతును గరిష్ట లోతుతో పోల్చి, దాన్ని నవీకరిస్తాము.

అల్గారిథం

  1. ఫంక్షన్ సృష్టించండి maxDepth () పై విధానంలో చర్చించినట్లు
  2. If రూట్ is శూన్య:
    • తిరిగి 0
  3. ప్రారంభించండి గరిష్ట లోతు మా ఫలితాన్ని నిల్వ చేయడానికి
  4. క్యూ ప్రారంభించండి అంశాలు చెట్టు నోడ్లు మరియు వాటి లోతులను కలిగి ఉంటుంది
  5. పుష్ రూట్ మరియు దాని లోతు 1 లోకి క్యూలో ఉంటుంది
  6. అయితే అంశాలు ఖాళీగా లేదు:
    • ముందు నోడ్ మరియు దాని ఎత్తును పొందండి ఫ్రంట్నోడ్ మరియు ఫ్రంట్‌నోడ్‌డెప్త్
    • క్యూ నుండి ఒక అంశాన్ని పాప్ చేయండి
    • If ఫ్రంట్‌నోడ్‌డెప్త్ is ఎక్కువ కంటే గరిష్ట లోతు
      1. నవీకరణ గరిష్టడెప్త్ = ఫ్రంట్నోడ్డెప్త్
    • If ఫ్రంట్నోడ్ is శూన్యమైనది కాదు:
      1. దాని పిల్లలందరినీ వారి లోతులతో క్యూలోకి నెట్టండి ఫ్రంట్‌నోడ్‌డెప్త్ + 1
  7. తిరిగి గరిష్ట లోతు
  8. ఫలితాన్ని ముద్రించండి

ఎన్-ఆరీ ట్రీ లీట్‌కోడ్ సొల్యూషన్ యొక్క గరిష్ట లోతు అమలు

సి ++ ప్రోగ్రామ్

#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

ఎన్-ఆరీ ట్రీ లీట్‌కోడ్ సొల్యూషన్ యొక్క గరిష్ట లోతు యొక్క సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

పై) మేము మళ్ళీ మొత్తం చెట్టును దాటుతున్నప్పుడు. N = చెట్టు యొక్క పరిమాణం

అంతరిక్ష సంక్లిష్టత

పై) చెట్టులోని అన్ని నోడ్‌లను వాటి లోతుతో నిల్వ చేయడానికి మేము క్యూను ఉపయోగిస్తున్నాము.