বাইনারি ট্রি লেটকোড সমাধানের ন্যূনতম গভীরতা


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় মর্দানী স্ত্রীলোক আপেল ফেসবুক
বাইনারি ট্রি প্রস্থ প্রথম অনুসন্ধান গভীরতা প্রথম অনুসন্ধান

এই সমস্যায়, আমাদের প্রদত্ত শিকড় থেকে যে কোনও পাতায় সবচেয়ে সংক্ষিপ্ত পথের দৈর্ঘ্য খুঁজে বের করতে হবে বাইনারি গাছ। মনে রাখবেন যে "পথের দৈর্ঘ্য" এর অর্থ এখানে মূল নোড থেকে পাতার নোড পর্যন্ত নোডের সংখ্যা। এই দৈর্ঘ্যকে একটি বাইনারি গাছের ন্যূনতম গভীরতা বলা হয়।

উদাহরণ

ইনপুট

বাইনারি ট্রি লেটকোড সমাধানের ন্যূনতম গভীরতা

 

 

 

 

 

 

 

2

ব্যাখ্যা

সংক্ষিপ্ততম পথটি হ'ল: 2 -> 1 , যার দৈর্ঘ্য 2

ইনপুট

 

 

 

 

 

 

 

3

ব্যাখ্যা

সবচেয়ে সংক্ষিপ্ত পথটি হ'ল: 1 -> 2 -> 3দৈর্ঘ্য 3

পন্থা (পুনরাবৃত্তি)

এই সমস্যাটি বাইনারি গাছের উচ্চতা সন্ধানের মতো কাঠামোগত একই তবে এই ক্ষেত্রে, আমাদের গাছের মূল এবং কোনও পাতার মধ্যে ন্যূনতম উচ্চতা / গভীরতা খুঁজে বের করতে হবে। আমরা ব্যবহার করে মূলের বাম এবং ডান সাবট্রির সর্বনিম্ন গভীরতা ফিরে পেতে পারি গভীরতা প্রথম অনুসন্ধান (ডিএফএস) এবং তারপরে দুটি গভীরতার সর্বনিম্ন ফিরিয়ে দিন। নোডের বাম এবং ডান সাবট্রির যে কোনও একটি যখন রয়েছে তখন আমাদের কিছু ক্ষেত্রে বিবেচনা করা উচিত শূন্য। বাম সাবট্রি যদি হয় খালি, এটি সমান উচ্চতা ফিরে আসবে তবে আমরা এই সাবট্রিতে কোনও পাতা পাই নি, সুতরাং এটি একটি ভুল উত্তর হবে। সুতরাং, আমাদের কেবল তখন পুনরাবৃত্ত ফাংশনটি কল করতে হবে যখন নোডটি ডাকা হয় না খালি.

অ্যালগরিদম

  1. একটি ফাংশন তৈরি করুন মিনিটপথ () পাসের মূলের সর্বনিম্ন গভীরতা ফিরিয়ে আনতে
  2. মূল যদি হয় শূন্য, ফিরে 0
  3. উভয় ক্ষেত্রে বাম এবং অধিকার সাবট্রিগুলি হ'ল শূন্য, ফিরুন 1
  4. বাম সাবট্রি যদি হয় শূন্য, ফিরে 1 + মিনিট ডেপথ (মূল-> ডান)
  5. অন্যথায় যদি সাবট্রি সঠিক হয় শূন্য, ফিরে 1 + minDepth (মূল-> বাম)
  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

বাইনারি ট্রি লেটকোড সমাধানের ন্যূনতম গভীরতার জটিলতা বিশ্লেষণ

সময় জটিলতা

চালু), যেমন আমরা সবচেয়ে খারাপ ক্ষেত্রে একবারে পুরো গাছটি অতিক্রম করি।

স্থান জটিলতা

চালু). যখন বাইনারি গাছটি স্কিউ হয়, পুনরাবৃত্তাকার স্ট্যাক ফ্রেমগুলি ও (এন) পর্যন্ত স্থান গ্রাস করতে পারে।

পন্থা (Iterative)

আমরা ব্যবহার করতে পারি প্রস্থ-প্রথম অনুসন্ধান (বিএফএস) প্রথম নোড যা একটি পাতাগুলি খুঁজে বের করতে এবং তার গভীর থেকে মূল থেকে ফিরে আসা। আমরা নোডগুলির একটি জোড়া এবং মূল নোড থেকে তাদের গভীরতা সঞ্চয় করতে একটি সারি ব্যবহার করতে পারি। যেহেতু আমরা কোনও নোড পাচ্ছি যা একটি পাতা, আমরা তার গভীরতা ফিরে পাই।

অ্যালগরিদম

  1. মূল যদি হয় শূন্য, ফিরে 0
  2. গাছের নোড এবং পূর্ণসংখ্যার জুটির একটি সারির সূচনা করুন
  3. এর গভীরতার সাথে কাতারে মূল নোডটি পুশ করুন 1
  4. সারিটি খালি নেই:
    • সামনের সারির উপাদানটির গভীরতা এবং নোডের ঠিকানা পুনরুদ্ধার করুন
    • সারি থেকে বাইরে একটি আইটেম পপ করুন
    • সামনের নোড হলে শূন্য, তার গভীরতা ফিরে
    • ধাক্কা বাম এবং অধিকার তারা যদি গাছের কাছে নোড দেয় না অকার্যকর
  5. প্রত্যাবর্তন -1 প্রোগ্রামটির বাক্য গঠন বজায় রাখতে যেমন ফাংশনটি পূর্ণসংখ্যা দেয় returns

বাইনারি ট্রি লেটকোড সমাধানের ন্যূনতম গভীরতার বাস্তবায়ন

সি ++ প্রোগ্রাম

#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

বাইনারি ট্রি লেটকোড সমাধানের ন্যূনতম গভীরতার জটিলতা বিশ্লেষণ

সময় জটিলতা

চালু), যেমন আমরা আবার পুরো গাছটি অতিক্রম করি।

স্থান জটিলতা

চালু), যেমন আমরা প্রতিটি নোডের বিশদ সঞ্চয় করতে একটি সারি ব্যবহার করি।