N-ary ट्री लीटकोड समाधानको अधिकतम गहराई


कठिनाई तह सजिलो
बारम्बार सोधिन्छ अमेजन गुगल माइक्रोसफ्ट
चौड़ाई पहिलो खोजी गहिराई पहिलो खोजी N-ary- रूख

यस समस्यामा, हामीलाई एक दिइन्छ N-ary रूख, त्यो हो, रूखले नोडहरूलाई २ भन्दा बढी बच्चा जन्माउँदछ। हामीले रूखको जराबाट पातको गहिराई पत्ता लगाउनु पर्छ। यसलाई अधिकतम गहिराई भनिन्छ। नोट गर्नुहोस् कि मार्गको गहिराइ यसमा नोडहरूको संख्या हो।

उदाहरणका

       2

  /    |    \

3      4      6

                \
           
                  9
3

स्पष्टीकरण: 9 मानको पात जराबाट टाढा छ र यसको गहिराई हो 3। त्यसो भए, हामी print प्रिन्ट गर्दछौं।

      2
  
  /      \

3           6   

        /   |   \

      4     7     9
3

स्पष्टीकरण: 4,7 र with मानको पातहरू जराबाट टाढा छन् र त्यसको गहिराई हो 3। त्यसो भए, हामी print प्रिन्ट गर्दछौं।

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

बाइनरी रूखको अधिकतम गहिराइ कुनै नोडको बायाँ र दायाँ बच्चाहरूलाई रिकर्सिभ प्रकार्य कल गरेर गणना गरिन्छ। त्यस्तै, N-ary रूखको मामलामा हामी कुनै पनि नोडका सबै बच्चाहरूमा रिकर्सिभ प्रकार्य कल गरेर अधिकतम गहिराइ गणना गर्न सक्छौं। यो दृष्टिकोण पुनरावर्ती छ र रूखको एक मात्र पास चाहिन्छ।

N-ary ट्री लीटकोड समाधानको अधिकतम गहराई

अल्गोरिदम

  1. प्रकार्य सिर्जना गर्नुहोस् maxDepth () एक रूख को अधिकतम गहिराई फर्काउन जसको मूल यसलाई पारित गरियो
  2. If मूल शून्य छ:
    • return
  3. भ्यारीएबल शुरुवात गर्नुहोस् MaxDepth N-ary रूखको अधिकतम गहिराई भण्डारण गर्न
  4. सबैको लागि बच्चा हालको जराको बच्चाहरूको सूचीमा:
    • सेट maxDepth = अधिकतम (maxDepth (root.left), maxDepth (root.right))
  5. फिर्ती अधिकतम डिप + 1

N-ary ट्री लीटकोड समाधानको अधिकतम गहराईको कार्यान्वयन

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

#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

जटिलता एन-अर्री ट्री लेटकोड समाधानको अधिकतम गहराईको विश्लेषण

समय जटिलता

O (N), N = N-ary रूखको आकार जब हामी एकपटक पूरै रूखलाई ट्रान्सभर्स गर्दछौं।

ठाउँ जटिलता

O (N) जब हामी रिकर्सिभ कलहरूको लागि मेमरीमा स्ट्याक फ्रेमहरू भण्डार गर्दछौं।

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

हामी माथिको प्रक्रिया पुनरावृत रूपमा गर्न सक्दछौं या त स्ट्याक वा पue्क्ति प्रयोग गरेर नोडहरू र तिनीहरूका गहिराइ जडबाट। अधिकतम गहराई यस प्रक्रियाबाट प्राप्त सबै जराको गहिराईको अधिकतम हुनेछ। हामी यस उद्देश्यका लागि लाम प्रयोग गर्छौं र रूखका सबै तत्त्वहरूलाई तिनीहरूको जराबाट गहिराइमा लाममा लान्छौं। हामी प्रत्येक नोडको गहिराईलाई अधिकतम गहिराईसँग तुलना गर्छौं र अपडेट गर्दछौं।

अल्गोरिदम

  1. प्रकार्य सिर्जना गर्नुहोस् maxDepth () माथिको दृष्टिकोणमा छलफल गरे जस्तो
  2. If मूल is खाली:
    • return
  3. आरम्भ गर्नुहोस् MaxDepth हाम्रो परिणाम भण्डारण गर्न
  4. एक पue्क्ति सुरूवात गर्नुहोस् तत्व यसले रूख नोडहरू र तिनीहरूको गहिराइ समावेश गर्दछ
  5. पुस मूल र यसको गहिराई लाई लाममा १
  6. जबकि तत्व खाली छैन:
    • अगाडि नोड र यसको उचाइ ल्याउनुहोस् फ्रन्टनोडfrontNodeDepth
    • लाम बाहिर लाइनमा एक वस्तु
    • If frontNodeDepth is अधिक भन्दा MaxDepth
      1. अपडेट maxDepth = frontNodeDepth
    • If फ्रन्टनोड is खाली छैन:
      1. यसका सबै बच्चाहरूलाई तिनीहरूका गहिराइको साथ लाममा लाममा लानुहोस् frontNodeDepth + 1
  7. फिर्ती MaxDepth
  8. परिणाम प्रिन्ट गर्नुहोस्

N-ary ट्री लीटकोड समाधानको अधिकतम गहराईको कार्यान्वयन

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

#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

जटिलता एन-अर्री ट्री लेटकोड समाधानको अधिकतम गहराईको विश्लेषण

समय जटिलता

O (N) जसरी हामी फेरि सम्पूर्ण रूख पार गर्दछौं। N = रूखको आकार

ठाउँ जटिलता

O (N) किनकी हामी रूखमा सबै नोडहरू तिनीहरूको गहिराइसँग भण्डार गर्न एक पue्क्ति प्रयोग गर्दछौं।