Максімальная глыбіня рашэння штрых-кода N-арнага дрэва


Узровень складанасці Лёгка
Часта пытаюцца ў амазонка Google Microsoft
Шырыня Першы пошук Глыбіня Першы пошук N-ары-дрэва

У гэтай праблеме нам дадзена Н-арнае дрэва, гэта значыць дрэва, якое дазваляе вузлам мець больш за 2 дзяцей. Нам трэба знайсці глыбіню ліста, самую аддаленую ад кораня дрэва. Гэта называецца максімальнай глыбінёй. Звярніце ўвагу, што глыбіня шляху - гэта колькасць вузлоў на ім.

Прыклад

       2

  /    |    \

3      4      6

                \
           
                  9
3

Тлумачэнне: Ліст з значэннем 9 знаходзіцца далей ад кораня і глыбіня яго 3. Такім чынам, мы друкуем 3.

      2
  
  /      \

3           6   

        /   |   \

      4     7     9
3

Тлумачэнне: Лісце з велічынёй 4,7 і 9 найбольш далёкія ад кораня, і іх глыбіня складае 3. Такім чынам, мы друкуем 3.

Падыход (Рэкурсіўны)

Максімальная глыбіня бінарнага дрэва вылічваецца шляхам выкліку рэкурсіўнай функцыі на левым і правым даччыных элементах любога вузла. Сапраўды гэтак жа, у выпадку N-арнага дрэва, мы можам вылічыць максімальную глыбіню, выклікаючы рэкурсіўную функцыю для ўсіх даччыных структур любога вузла. Такі падыход з'яўляецца рэкурсіўным і патрабуе толькі аднаго праходжання дрэва.

Максімальная глыбіня рашэння штрых-кода N-арнага дрэва

Алгарытм

  1. Стварыце функцыю максімальная глыбіня () каб вярнуць максімальную глыбіню дрэва, чыя корань перадаецца яму
  2. If корань нуль:
    • return 0
  3. Ініцыялізуйце зменную максімальная глыбіня для захоўвання максімальнай глыбіні N-арнага дрэва
  4. для кожнага дзіця у даччыным спісе бягучага кораня:
    • камплект максімальная глыбіня = максімальная (максімальная глыбіня (корань.лева), максімальная глыбіня (корань.права))
  5. вяртаць максімальная глыбіня + 1

Укараненне максімальнай глыбіні рашэння штрых-кода N-арнага дрэва

Праграма 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;
}

Праграма Java

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-арнага дрэва

Складанасць часу

O (N), N = памер N-арнага дрэва, калі мы перасякаем цэлае дрэва адзін раз.

Касмічная складанасць

O (N) паколькі мы захоўваем кадры стэка ў памяці для рэкурсіўных выклікаў.

Падыход (Ітэратыўны)

Мы можам зрабіць вышэйапісаны працэс ітэрацыйна, выкарыстоўваючы альбо стэк, альбо чаргу для захоўвання вузлоў і іх глыбінь ад кораня. Максімальная глыбіня будзе максімальнай глыбінёй усіх каранёў, атрыманых у выніку гэтага працэсу. Для гэтага мы выкарыстоўваем чаргу і выштурхоўваем усе элементы дрэва ў чаргу разам з іх глыбінёй ад кораня. Мы параўноўваем глыбіню кожнага вузла з максімальнай глыбінёй і абнаўляем яе.

Алгарытм

  1. Стварыце функцыю максімальная глыбіня () падобна таму, як абмяркоўвалася ў вышэйзгаданым падыходзе
  2. If корань is нуль:
    • return 0
  3. Ініцыялізацыя максімальная глыбіня для захоўвання нашага выніку
  4. Ініцыялізацыя чаргі элементы які змяшчае вузлы дрэў і іх глыбіню
  5. Штурхаць корань і яго глыбіня як 1 у чаргу
  6. У той час як элементы не пусты:
    • Дастаньце пярэдні вузел і яго вышыню як frontNode і frontNodeDepth
    • Выдаліць элемент з чаргі
    • If frontNodeDepth is вялікі чым максімальная глыбіня
      1. абнаўленне maximumDepth = frontNodeDepth
    • If frontNode is не null:
      1. Падштурхнуць усіх сваіх дзяцей у чаргу з іх глыбінёй як frontNodeDepth 1 +
  7. вяртаць максімальная глыбіня
  8. Раздрукуйце вынік

Укараненне максімальнай глыбіні рашэння штрых-кода N-арнага дрэва

Праграма 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;
}

Праграма Java

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-арнага дрэва

Складанасць часу

O (N) як мы зноў перабягаем усё дрэва. N = памер дрэва

Касмічная складанасць

O (N) паколькі мы выкарыстоўваем чаргу для захоўвання ўсіх вузлоў у дрэве з іх глыбінёй.