მინიმალური სიღრმე ორობითი ხის Leetcode გადაწყვეტა  


Რთული ტური Easy
ხშირად ეკითხებიან Amazon Apple Facebook
ალგორითმები ორობითი ხე სიგანე პირველი ძებნა კოდირება სიღრმისეული პირველი ძებნა ინტერვიუ ინტერვიუს მოსამზადებელი LeetCode LeetCodeSolutions

ამ პრობლემის დროს, ჩვენ უნდა ვიპოვოთ უმოკლესი ბილიკის სიგრძე ფესვიდან მოცემულ მოცემულ ფოთოლამდე ორობითი ხე. გაითვალისწინეთ, რომ აქ ”ბილიკის სიგრძე” ნიშნავს კვანძების რაოდენობას ფესვის კვანძიდან ფოთლის კვანძამდე. ამ სიგრძეს ეწოდება ორობითი ხის მინიმალური სიღრმე.

მაგალითი  

შეყვანის

მინიმალური სიღრმე ორობითი ხის Leetcode გადაწყვეტაPin

 

 

 

 

 

 

 

2

განმარტება

უმოკლესი გზაა: 2 -> 1 , რომლის სიგრძეა 2

შეყვანის

 

 

 

 

 

 

 

3

განმარტება

უმოკლესი გზაა: 1 -> 2 -> 3, სიგრძის 3

მიდგომა (რეკურსიული)  

ეს პრობლემა სტრუქტურულად იგივეა, როგორც ორობითი ხის სიმაღლის პოვნა, მაგრამ ამ შემთხვევაში, ჩვენ უნდა ვიპოვნოთ მინიმალური სიმაღლე / სიღრმე ფესვსა და ხის ნებისმიერ ფოთოლს შორის. ჩვენ შეგვიძლია მივიღოთ ფესვის მარცხენა და მარჯვენა ქვეტყის მინიმალური სიღრმეები სიღრმისეული პირველი ძებნა (DFS) და შემდეგ დააბრუნეთ ორი სიღრმის მინიმუმი. უნდა განვიხილოთ რამდენიმე შემთხვევა, როდესაც კვანძის რომელიმე მარცხენა და მარჯვენა ქვეტყეა NULL. თუ მარცხენა ქვეტყეა NULL, ის დააბრუნებს ტოლს მაგრამ, რადგან ამ ქვეჯგუფში ვერ ვხვდებით ფოთოლს, ასე რომ, ეს არის არასწორი პასუხი იქნება. მაშასადამე, საჭიროა მხოლოდ რეკურსიული ფუნქციის გამოძახება, როდესაც ის კვანძია არა ნულოვანი.

იხილეთ ასევე
Pascal's Triangle II Leetcode Solution

ალგორითმი

  1. ფუნქციის შექმნა minDepth () გადაბრუნებული ფესვის მინიმალური სიღრმის დასაბრუნებლად
  2. თუ ფესვი არის NULL, დაბრუნების
  3. იმ შემთხვევაში, თუ ორივე დარჩა და უფლება ქვეტყეებია NULL, დაბრუნება 1
  4. თუ მარცხენა ქვეტყეა NULL, დაბრუნების 1 + წთ სიღრმე (root-> მარჯვნივ)
  5. სხვა შემთხვევაში თუ არის სწორი ქვეტყე NULL, დაბრუნების 1 + წთ სიღრმე (root-> მარცხნივ)
  6. დაბრუნება 1 + მინიმალური (წთ სიღრმე(root-> მარცხნივ), წთ სიღრმე(root-> მარჯვნივ))

ორობითი ხის 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';
}

ჯავა პროგრამა

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), როგორც უარყოფით შემთხვევაშიც კი ერთხელ ხეზე გავდივართ.

კოსმოსური სირთულის

O (N) როდესაც ორობითი ხე გადახრილია, რეკურსიული დასტის ჩარჩოებმა შეიძლება მოიხმარონ O (N) სივრცეში.

იხილეთ ასევე
შექმენით სიმები სიმბოლოებით, რომლებსაც აქვთ უცნაური რიცხვების Leetcode ამოხსნა

მიდგომა (განმეორებითი)  

ჩვენ შეგვიძლია გამოვიყენოთ სიგანის პირველი ძებნა (BFS) იპოვონ პირველი კვანძი, რომელიც არის ფოთოლი და დაუბრუნონ მისი სიღრმე ფესვიდან. რიგის გამოყენებით შეგვიძლია შევინახოთ წყვილი კვანძი და მათი სიღრმე ფესვის კვანძიდან. ვიღებთ კვანძს, რომელიც ფოთოლია, ჩვენ ვუბრუნდებით მის სიღრმეს.

ალგორითმი

  1. თუ ფესვი არის NULL, დაბრუნების
  2. ხეების კვანძების და მთელი რიცხვების რიგის ინიციალიზაცია
  3. ძირეული კვანძი რიგისკენ მიიტანეთ მისი სიღრმით 1
  4. მიუხედავად იმისა, რომ რიგი არ არის ცარიელი:
    • წინა რიგის ელემენტის სიღრმისა და კვანძის მისამართის მიღება
    • გამოყავით ნივთი რიგიდან
    • თუ წინა კვანძია NULL, დააბრუნე მისი სიღრმე
    • დააყენებს დარჩა და უფლება კვანძები ხისკენ, თუ ისინი არიან არ 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';
}


ჯავა პროგრამა

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 ხსნარის მინიმალური სიღრმის სირთულის ანალიზი

დროის სირთულე

O (N), როდესაც კიდევ ერთხელ გადავკვეთთ მთელს ხეს.

იხილეთ ასევე
საბოლოო ფასები სპეციალური ფასდაკლებით მაღაზიაში Leetcode Solution

კოსმოსური სირთულის

O (N), რადგან ჩვენ ვიყენებთ რიგს თითოეული კვანძის დეტალების შესანახად.