Максимална дубина Нет-а Трее Леетцоде решења


Ниво тешкоће Лако
Често питани у амазонка гоогле мицрософт
Претрага у ширину Дубина прва претрага Н-ар-дрво

У овом проблему добијамо Н-арно дрво, односно дрво које омогућава чворовима да имају више од 2 деце. Морамо пронаћи дубину листа најудаљенијег од корена дрвета. То се назива максимална дубина. Имајте на уму да је дубина путање број чворова на њој.

Пример

       2

  /    |    \

3      4      6

                \
           
                  9
3

Објашњење: Лист са вредношћу 9 је најудаљенији од корена и његова дубина је 3. Дакле, штампамо 3.

      2
  
  /      \

3           6   

        /   |   \

      4     7     9
3

Објашњење: Листови вредности 4,7 и 9 су најудаљенији од корена и њихова дубина је 3. Дакле, штампамо 3.

Приступ(Рекурзивно)

Максимална дубина бинарног стабла израчунава се позивањем рекурзивне функције на левом и десном подређеном било ког чвора. Слично томе, у случају Н-арног стабла, можемо израчунати максималну дубину позивањем рекурзивне функције на свим подређеним целинама било којег чвора. Овај приступ је рекурзиван и захтева само један пролазак стабла.

Максимална дубина Нет-а Трее Леетцоде решења

Алгоритам

  1. Направите функцију макДептх () да се врати максимална дубина дрвета чија корен се преноси на њега
  2. If корен је нулл:
    • врати КСНУМКС
  3. Иницијализујте променљиву макимумДептх за чување максималне дубине Н-арног дрвета
  4. За сваки дете на подређеној листи тренутног корена:
    • сет макимумДептх = мак (макДептх (роот.лефт), макДептх (роот.ригхт))
  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

Анализа сложености максималне дубине решења Леетцоде Н-арри дрвета

Сложеност времена

О (Н), Н. = величина Н-арног дрвета док једном прелазимо цело дрво.

Сложеност простора

НА) док у меморију складиштимо оквире стека за рекурзивне позиве.

Приступ(Итеративно)

Горе наведени поступак можемо поновити итеративно користећи стек или ред за чување чворова и њихових дубина од корена. Максимална дубина биће максимална дубина свих корена добијених у овом процесу. У ту сврху користимо ред и гурамо све елементе стабла у ред заједно са њиховим дубинама од корена. Дубину сваког чвора упоређујемо са максималном дубином и ажурирамо је.

Алгоритам

  1. Креирајте функцију макДептх () слично као што је разматрано у горњем приступу
  2. If корен is нула:
    • врати КСНУМКС
  3. Инитиалисе макимумДептх да чувамо наш резултат
  4. Иницирајте ред елементи који садржи чворове стабала и њихове дубине
  5. гурање корен а његова дубина као 1 у ред
  6. Док елементи није празно:
    • Дохватите предњи чвор и његову висину као фронтНоде фронтНодеДептх
    • Избаците ставку из реда
    • If фронтНодеДептх is већа него макимумДептх
      1. ажурирање макимумДептх = фронтНодеДептх
    • If фронтНоде is није нулл:
      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

Анализа сложености максималне дубине решења Леетцоде Н-арри дрвета

Сложеност времена

НА) док опет прелазимо цело дрво. Н = величина стабла

Сложеност простора

НА) као што користимо ред за чување свих чворова у стаблу са њиховим дубинама.