Минимална дубина решења са бинарним стаблом са кодом


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

У овом проблему морамо да пронађемо дужину најкраћег пута од корена до било ког листа у датом бинарно стабло. Имајте на уму да овде „дужина путање“ значи број чворова од коренског до чворног листа. Ова дужина се назива Минимална дубина бинарног стабла.

Пример

Улазни

Минимална дубина решења са бинарним стаблом са кодом

 

 

 

 

 

 

 

2

Објашњење

Најкраћи пут је: 2 -> 1 , која је дужине 2

Улазни

 

 

 

 

 

 

 

3

Објашњење

Најкраћи пут је: 1 -> 2 -> 3, дужине 3

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

Овај проблем је структурно исти као и проналажење висине бинарног стабла, али у овом случају морамо пронаћи минималну висину / дубину између корена и било ког листа на дрвету. Помоћу можемо да дохватимо минималне дубине левог и десног подстабла корена Дубина прво претраживање (ДФС) а затим вратите минимум од две дубине. Морамо да размотримо неке случајеве када је било које од левог и десног подстабла чвора НУЛЛ. Ако је лево подстабло НУЛА, вратиће висину једнаку али како у овом подстаблу нисмо пронашли лист, тако и ово биће погрешан одговор. Стога рекурзивну функцију треба да позовемо само када је чвор на који се позива НЕ нула.

Алгоритам

  1. Направите функцију минДептх () да се врати минимална дубина пређеног корена
  2. Ако је корен НУЛЛ, повратак 0
  3. У случају да оба left (остављено) у праву подстабла су НУЛЛ, повратак 1
  4. Ако је лево подстабло НУЛЛ, повратак 1 + минДубина (корен-> десно)
  5. У супротном случају право поддрво је НУЛЛ, повратак 1 + минДупљина (корен-> лево)
  6. Поврат 1 + минимум (минДептх(корен-> лево), минДептх(корен-> десно))

Имплементација минималне дубине решења са бинарним стаблом са кодовима

Програм Ц ++

#include <bits/stdc++.h>
using namespace std;
struct treeNode
{
    int value;
    treeNode *left , *right;
    treeNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};

int minDepth(treeNode* root)
{
    if(root == NULL)
        return 0;
    if(root->left == NULL && root->right == NULL)
        return 1;
    if(root->left == NULL)
        return 1 + minDepth(root->right);
    if(root->right == NULL)
        return 1 + minDepth(root->left);
    return 1 + min(minDepth(root->left) , minDepth(root->right));
}

int main()
{
    treeNode* root = new treeNode(2);
    root->left = new treeNode(1);
    root->right = new treeNode(3);
    root->right->left = new treeNode(4);
    root->right->right = new treeNode(5);
    cout << minDepth(root) << '\n';
}

Јава Програм

import java.util.*;

class treeNode
{
    int value;
    treeNode left, right;
    public treeNode(int x)
    {
        value = x;
        left = right = null;
    }
}

class Pair
{
    treeNode key;
    int value;

    Pair(treeNode root , int val)
    {
        key = root;
        value = val;
    }
}

class Minimum_Depth_Of_A_Binary_Tree
{
    public static void main(String args[])
    {
        treeNode root = new treeNode(2);
        root.left = new treeNode(1);
        root.right = new treeNode(3);
        root.right.left = new treeNode(4);
        root.right.right = new treeNode(5);
        System.out.println(minDepth(root));
    }

    static int minDepth(treeNode root)
    {
        if(root == null)
            return 0;
        if(root.left == null && root.right == null)
            return 1;
        if(root.left == null)
            return 1 + minDepth(root.right);
        if(root.right == null)
            return 1 + minDepth(root.left);
        return 1 + Math.min(minDepth(root.left) , minDepth(root.right));

    }
}
2

Анализа сложености минималне дубине решења бинарног стабла са шифром

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

НА), док једном прелазимо цело дрво чак и у најгорем случају.

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

НА). Када је бинарно стабло искошено, рекурзивни оквири стека могу потрошити до О (Н) простора.

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

Можемо користити Ширина-прва претрага (БФС) пронаћи први чвор који је лист и вратити његову дубину од корена. Ред можемо користити за чување пара чворова и њихових дубина од коренског чвора. Како примамо чвор који је лист, враћамо му дубину.

Алгоритам

  1. Ако је роот НУЛЛ, повратак 0
  2. Иницијализујте ред од пар чворова стабла и целих бројева
  3. Гурните коријенски чвор у ред са његовом дубином као 1
  4. Иако ред није празан:
    • Дохватите дубину и адресу чвора елемента предњег реда
    • Избаците ставку из реда
    • Ако је предњи чвор НУЛЛ, вратите му дубину
    • Притисни left (остављено) у праву чворови на дрвету ако јесу не нула
  5. повратак -1 за одржавање синтаксе програма јер функција враћа цео број

Имплементација минималне дубине решења са бинарним стаблом са кодовима

Програм Ц ++

#include <bits/stdc++.h>
using namespace std;
struct treeNode
{
    int value;
    treeNode *left , *right;
    treeNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};

int minDepth(treeNode* root)
{
    if(root == NULL)
        return 0;
    queue < pair <treeNode* , int> > q;
    q.push({root , 1});

    treeNode* frontNode;
    int depth;

    while(!q.empty())
    {
        frontNode = q.front().first;
        depth = q.front().second;
        q.pop();

        if(frontNode->left == NULL && frontNode->right == NULL)
            return depth;

        if(frontNode->left != NULL)
            q.push({frontNode->left , depth + 1});

        if(frontNode->right != NULL)
            q.push({frontNode->right , depth + 1});
    }
    return -1;
}

int main()
{
    treeNode* root = new treeNode(2);
    root->left = new treeNode(1);
    root->right = new treeNode(3);
    root->right->left = new treeNode(4);
    root->right->right = new treeNode(5);
    cout << minDepth(root) << '\n';
}


Јава Програм

import java.util.*;

class treeNode
{
    int value;
    treeNode left, right;
    public treeNode(int x)
    {
        value = x;
        left = right = null;
    }
}

class Pair
{
    treeNode key;
    int value;

    Pair(treeNode root , int val)
    {
        key = root;
        value = val;
    }
}

class Minimum_Depth_Of_A_Binary_Tree
{
    public static void main(String args[])
    {
        treeNode root = new treeNode(2);
        root.left = new treeNode(1);
        root.right = new treeNode(3);
        root.right.left = new treeNode(4);
        root.right.right = new treeNode(5);
        System.out.println(minDepth(root));
    }

    static int minDepth(treeNode root)
    {
        if(root == null)
            return 0;
        LinkedList <Pair> q = new LinkedList<>();
        q.add(new Pair(root , 1));

        treeNode frontNode;
        int depth;

        while(q.size() > 0)
        {
            frontNode = q.peek().key;
            depth = q.peek().value;

            q.remove();

            if(frontNode.left == null && frontNode.right == null)
                return depth;

            if(frontNode.left != null)
                q.add(new Pair(frontNode.left , depth + 1));

            if(frontNode.right != null)
                q.add(new Pair(frontNode.right , depth + 1));
        }
        return -1;
    }
}
2

Анализа сложености минималне дубине решења бинарног стабла са шифром

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

НА), док још једном прелазимо цело дрво.

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

НА), јер користимо ред за чување детаља сваког чвора.