Минимална дълбочина на решението с двоично дърво Leetcode


Ниво на трудност Лесно
Често задавани в Амазонка ябълка Facebook
Двоично дърво Широчина Първо търсене Дълбочина Първо търсене

В този проблем трябва да намерим дължината на най-краткия път от корена до всеки лист в даден двоично дърво. Имайте предвид, че „дължината на пътя“ тук означава броя на възлите от основния възел до листния възел. Тази дължина се нарича Минимална дълбочина на двоично дърво.

Пример

Вход

Минимална дълбочина на решението с двоично дърво Leetcode

 

 

 

 

 

 

 

2

Обяснение

Най-краткият път е: 2 -> 1 , която е с дължина 2

Вход

 

 

 

 

 

 

 

3

Обяснение

Най-краткият път е: 1 -> 2 -> 3, с дължина 3

Подход (рекурсивен)

Този проблем структурно е същият като намирането на височината на двоично дърво, но в този случай трябва да намерим минималната височина / дълбочина между корена и всеки лист в дървото. Можем да извлечем минималната дълбочина на ляво и дясно поддървета на корен, използвайки Дълбочина първо търсене (DFS) и след това върнете минимума от двете дълбочини. Трябва да разгледаме някои случаи, когато е едно от лявото и дясното поддърво на възел NULL. Ако лявото поддърво е НУЛА, ще върне височина, равна на но тъй като не сме намерили лист в това поддърво, така и това ще бъде грешен отговор. Следователно, трябва да извикаме рекурсивната функция само когато възелът, към който е извикан, е НЕ нула.

алгоритъм

  1. Създайте функция minDepth () за връщане на минималната дълбочина на преминатия корен
  2. Ако коренът е NULL, връщане 0
  3. В случай, че и двете наляво и прав поддървета са NULL, връщане 1
  4. Ако лявото поддърво е NULL, връщане 1 + минДълбочина (корен-> вдясно)
  5. В противен случай правилното поддърво е NULL, връщане 1 + минДълбочина (корен-> ляво)
  6. Връщане 1 + минимум (minDepth(корен-> ляво), minDepth(корен-> вдясно))

Внедряване на минимална дълбочина на решението с двоично дърво Leetcode

Програма C ++

#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';
}

Програма Java

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

Анализ на сложността на минималната дълбочина на решението с двоично дърво Leetcode

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

НА), тъй като прекосяваме цялото дърво веднъж дори в най-лошия случай.

Космическа сложност

НА). Когато двоичното дърво е изкривено, рекурсивните рамки на стека могат да изразходват до O (N) пространство.

Подход (итеративен)

Ние можем да използваме Широко-първо търсене (BFS) за да намерите първия възел, който е лист и да върнете дълбочината му от корена. Можем да използваме опашка за съхраняване на двойка възли и техните дълбочини от основния възел. Когато получим възел, който е лист, ние връщаме дълбочината му.

алгоритъм

  1. Ако коренът е NULL, връщане 0
  2. Инициализирайте опашка от двойка дървовидни възли и цели числа
  3. Натиснете коренния възел към опашката с дълбочината му като 1
  4. Докато опашката не е празна:
    • Извличане на дълбочината и адреса на възела на елемента от предната опашка
    • Изпратете елемент от опашката
    • Ако предният възел е NULL, върнете дълбочината му
    • Натиснете наляво и прав възли към дървото, ако са не нула
  5. връщане -1 за да поддържа синтаксиса на програмата, тъй като функцията връща цяло число

Внедряване на минимална дълбочина на решението с двоично дърво Leetcode

Програма C ++

#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';
}


Програма Java

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

Анализ на сложността на минималната дълбочина на решението с двоично дърво Leetcode

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

НА), докато прекосяваме цялото дърво за пореден път.

Космическа сложност

НА), тъй като използваме опашка за съхраняване на подробности за всеки възел.