N-ary மரம் லீட்கோட் தீர்வின் அதிகபட்ச ஆழம்


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அமேசான் கூகிள் மைக்ரோசாப்ட்
அகலம் முதல் தேடல் ஆழம் முதல் தேடல் என்-ஆரி-மரம்

இந்த சிக்கலில், எங்களுக்கு ஒரு வழங்கப்படுகிறது என்-ஆரி மரம்அதாவது, முனைகளுக்கு 2 க்கும் மேற்பட்ட குழந்தைகளைப் பெற அனுமதிக்கும் ஒரு மரம். மரத்தின் வேரிலிருந்து ஒரு இலையின் ஆழத்தை நாம் கண்டுபிடிக்க வேண்டும். இது அதிகபட்ச ஆழம் என்று அழைக்கப்படுகிறது. ஒரு பாதையின் ஆழம் அதில் உள்ள முனைகளின் எண்ணிக்கை என்பதை நினைவில் கொள்க.

உதாரணமாக

       2

  /    |    \

3      4      6

                \
           
                  9
3

விளக்கம்: மதிப்பு 9 கொண்ட இலை வேரிலிருந்து வெகு தொலைவில் உள்ளது மற்றும் அதன் ஆழம் 3. எனவே, நாங்கள் 3 ஐ அச்சிடுகிறோம்.

      2
  
  /      \

3           6   

        /   |   \

      4     7     9
3

விளக்கம்: 4,7 மற்றும் 9 மதிப்புள்ள இலைகள் வேரிலிருந்து வெகு தொலைவில் உள்ளன மற்றும் அவற்றின் ஆழம் 3. எனவே, நாங்கள் 3 ஐ அச்சிடுகிறோம்.

அணுகுமுறை (மீளுருவாக்க)

பைனரி மரத்தின் அதிகபட்ச ஆழம் எந்த முனையின் இடது மற்றும் வலது குழந்தைகளில் சுழல்நிலை செயல்பாட்டை அழைப்பதன் மூலம் கணக்கிடப்படுகிறது. இதேபோல், ஒரு N-ary மரத்தின் விஷயத்தில், எந்தவொரு முனையின் அனைத்து குழந்தைகளிலும் சுழல்நிலை செயல்பாட்டை அழைப்பதன் மூலம் அதிகபட்ச ஆழத்தை கணக்கிடலாம். இந்த அணுகுமுறை சுழல்நிலை மற்றும் மரத்தின் ஒரு பாஸ் மட்டுமே தேவைப்படுகிறது.

N-ary மரம் லீட்கோட் தீர்வின் அதிகபட்ச ஆழம்

அல்காரிதம்

  1. ஒரு செயல்பாட்டை உருவாக்கவும் maxDepth () ஒரு மரத்தின் அதிகபட்ச ஆழத்தை திருப்புவதற்கு ரூட் அதற்கு அனுப்பப்படுகிறது
  2. If ரூட் பூஜ்யமானது:
    • திரும்ப 0
  3. ஒரு மாறியைத் தொடங்கவும் அதிகபட்ச அளவு N-ary மரத்தின் அதிகபட்ச ஆழத்தை சேமிக்க
  4. ஒவ்வொரு குழந்தை தற்போதைய மூலத்தின் குழந்தைகள் பட்டியலில்:
    • தொகுப்பு maxDepth = அதிகபட்சம் (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-ary மரத்தின் அளவு.

விண்வெளி சிக்கலானது

ஓ (என்) சுழல்நிலை அழைப்புகளுக்கு நினைவகத்தில் ஸ்டேக் பிரேம்களை சேமிக்கும்போது.

அணுகுமுறை (மறுநிகழ்)

முனைகள் மற்றும் அவற்றின் ஆழத்தை வேரிலிருந்து சேமிக்க ஒரு அடுக்கு அல்லது வரிசையைப் பயன்படுத்துவதன் மூலம் மேலே உள்ள செயல்முறையை நாம் மீண்டும் செய்ய முடியும். இந்த செயல்முறையிலிருந்து பெறப்பட்ட அனைத்து வேர்களின் ஆழத்தின் அதிகபட்ச ஆழம் அதிகபட்சமாக இருக்கும். இந்த நோக்கத்திற்காக நாங்கள் ஒரு வரிசையைப் பயன்படுத்துகிறோம், மேலும் மரத்தின் அனைத்து உறுப்புகளையும் வேரில் இருந்து அவற்றின் ஆழத்துடன் வரிசையில் தள்ளுகிறோம். ஒவ்வொரு முனையின் ஆழத்தையும் அதிகபட்ச ஆழத்துடன் ஒப்பிட்டு புதுப்பிக்கிறோம்.

அல்காரிதம்

  1. செயல்பாட்டை உருவாக்கவும் maxDepth () மேலே உள்ள அணுகுமுறையில் விவாதிக்கப்பட்டதைப் போன்றது
  2. If ரூட் is ஏதுமில்லை:
    • திரும்ப 0
  3. துவக்க அதிகபட்ச அளவு எங்கள் முடிவை சேமிக்க
  4. ஒரு வரிசையைத் தொடங்கவும் கூறுகள் இது மர முனைகள் மற்றும் அவற்றின் ஆழங்களைக் கொண்டுள்ளது
  5. புஷ் ரூட் மற்றும் அதன் ஆழம் வரிசையில் 1 ஆக இருக்கும்
  6. போது கூறுகள் காலியாக இல்லை:
    • முன் முனை மற்றும் அதன் உயரத்தைப் பெறுங்கள் frontNode மற்றும் frontNodeDepth
    • வரிசையில் இருந்து ஒரு உருப்படியை பாப் செய்யவும்
    • If frontNodeDepth is அதிக விட அதிகபட்ச அளவு
      1. புதுப்பிக்கப்பட்டது MaxDepth = frontNodeDepth
    • If frontNode is பூஜ்யமாக இல்லை:
      1. அதன் எல்லா குழந்தைகளையும் அவர்களின் ஆழத்துடன் வரிசையில் தள்ளுங்கள் frontNodeDepth + 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 = மரத்தின் அளவு

விண்வெளி சிக்கலானது

ஓ (என்) மரத்தில் உள்ள அனைத்து முனைகளையும் அவற்றின் ஆழத்துடன் சேமிக்க வரிசையைப் பயன்படுத்துகிறோம்.