ബൈനറി ട്രീ ലീറ്റ്കോഡ് പരിഹാരത്തിന്റെ ഏറ്റവും കുറഞ്ഞ ആഴം


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ആമസോൺ ആപ്പിൾ ഫേസ്ബുക്ക്
ബൈനറി ട്രീ വീതിയുടെ ആദ്യ തിരയൽ ആഴത്തിലുള്ള ആദ്യ തിരയൽ

ഈ പ്രശ്‌നത്തിൽ, ഒരു നിശ്ചിത ഭാഗത്തിൽ നിന്ന് ഏതെങ്കിലും ഇലയിലേക്കുള്ള ഏറ്റവും ചെറിയ പാതയുടെ ദൈർഘ്യം ഞങ്ങൾ കണ്ടെത്തേണ്ടതുണ്ട് ബൈനറി ട്രീ. ഇവിടെ “പാതയുടെ ദൈർഘ്യം” എന്നതിനർത്ഥം റൂട്ട് നോഡിൽ നിന്ന് ലീഫ് നോഡിലേക്കുള്ള നോഡുകളുടെ എണ്ണം എന്നാണ്. ഈ നീളത്തെ ഒരു ബൈനറി ട്രീയുടെ മിനിമം ഡെപ്ത് എന്ന് വിളിക്കുന്നു.

ഉദാഹരണം

ഇൻപുട്ട്

ബൈനറി ട്രീ ലീറ്റ്കോഡ് പരിഹാരത്തിന്റെ ഏറ്റവും കുറഞ്ഞ ആഴം

 

 

 

 

 

 

 

2

വിശദീകരണം

ഏറ്റവും ചെറിയ പാത ഇതാണ്: 2 -> 1 , അതിന്റെ നീളം 2 ആണ്

ഇൻപുട്ട്

 

 

 

 

 

 

 

3

വിശദീകരണം

ഏറ്റവും ചെറിയ പാത ഇതാണ്: 1 -> 2 -> 3, നീളം 3

സമീപനം (ആവർത്തന)

ഈ പ്രശ്നം ഘടനാപരമായി ഒരു ബൈനറി വൃക്ഷത്തിന്റെ ഉയരം കണ്ടെത്തുന്നതിന് തുല്യമാണ്, എന്നാൽ ഈ സാഹചര്യത്തിൽ, റൂട്ടിനും വൃക്ഷത്തിലെ ഏതെങ്കിലും ഇലയ്ക്കും ഇടയിലുള്ള ഏറ്റവും കുറഞ്ഞ ഉയരം / ആഴം കണ്ടെത്തേണ്ടതുണ്ട്. റൂട്ടിന്റെ ഇടത്, വലത് സബ്‌ട്രീകളുടെ ഏറ്റവും കുറഞ്ഞ ആഴം നമുക്ക് വീണ്ടെടുക്കാൻ കഴിയും ആഴത്തിലുള്ള ആദ്യ തിരയൽ (DFS) എന്നിട്ട് രണ്ട് ആഴങ്ങളിൽ ഏറ്റവും കുറഞ്ഞത് നൽകുക. ഒരു നോഡിന്റെ ഇടത്, വലത് സബ്‌ട്രീസുകളിൽ ഒന്നായിരിക്കുമ്പോൾ ഞങ്ങൾ ചില കേസുകൾ പരിഗണിക്കേണ്ടതുണ്ട് NULL. ഇടത് സബ്‌ട്രീ ആണെങ്കിൽ ശൂന്യം, അത് തുല്യമായ ഉയരം നൽകും എന്നാൽ ഈ സബ്‌ട്രീയിൽ ഒരു ഇലയും ഞങ്ങൾ കണ്ടെത്തിയിട്ടില്ലാത്തതിനാൽ ഇത് ഒരു തെറ്റായ ഉത്തരമായിരിക്കും. അതിനാൽ, ആവർത്തന ഫംഗ്ഷനെ നോഡ് വിളിക്കുമ്പോൾ മാത്രമേ ഞങ്ങൾ അത് വിളിക്കൂ ചെയ്യില്ല ശൂന്യം.

അൽഗോരിതം

  1. ഒരു ഫംഗ്ഷൻ സൃഷ്ടിക്കുക minDepth () കടന്നുപോയ റൂട്ടിന്റെ ഏറ്റവും കുറഞ്ഞ ഡെപ്ത് നൽകുന്നതിന്
  2. റൂട്ട് ആണെങ്കിൽ NULL, മടങ്ങുക 0
  3. രണ്ടും രണ്ടും ഇടത്തെ ഒപ്പം വലത് സബ്‌ട്രീസുകൾ NULL, മടങ്ങുക 1
  4. ഇടത് സബ്‌ട്രീ ആണെങ്കിൽ NULL, മടങ്ങുക 1 + minDepth (റൂട്ട്-> വലത്)
  5. ശരിയായ സബ്‌ട്രീ ആണെങ്കിൽ മറ്റൊന്ന് NULL, മടങ്ങുക 1 + minDepth (റൂട്ട്-> ഇടത്)
  6. കുറഞ്ഞത് 1 + മടങ്ങുക (minDepth(റൂട്ട്-> ഇടത്), minDepth(റൂട്ട്-> വലത്))

ബൈനറി ട്രീ ലീറ്റ്കോഡ് പരിഹാരത്തിന്റെ ഏറ്റവും കുറഞ്ഞ ആഴം നടപ്പിലാക്കൽ

സി ++ പ്രോഗ്രാം

#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

ബൈനറി ട്രീ ലീറ്റ്കോഡ് പരിഹാരത്തിന്റെ ഏറ്റവും കുറഞ്ഞ ആഴത്തിന്റെ സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (N), ഏറ്റവും മോശം അവസ്ഥയിൽപ്പോലും ഞങ്ങൾ മുഴുവൻ വൃക്ഷവും സഞ്ചരിക്കുമ്പോൾ.

സ്ഥല സങ്കീർണ്ണത

O (N). ബൈനറി ട്രീ വളച്ചൊടിക്കുമ്പോൾ, ആവർത്തന സ്റ്റാക്ക് ഫ്രെയിമുകൾ O (N) ഇടം വരെ ഉപയോഗിച്ചേക്കാം.

സമീപനം (ആവർത്തനം)

നമുക്ക് ഉപയോഗിക്കാം വീതി-ആദ്യ തിരയൽ (BFS) ഒരു ഇലയായ ആദ്യത്തെ നോഡ് കണ്ടെത്താനും അതിന്റെ ആഴം റൂട്ടിൽ നിന്ന് തിരികെ നൽകാനും. റൂട്ട് നോഡിൽ നിന്ന് ഒരു ജോഡി നോഡുകളും അവയുടെ ആഴവും സംഭരിക്കാൻ നമുക്ക് ഒരു ക്യൂ ഉപയോഗിക്കാം. ഒരു ഇലയായ ഒരു നോഡ് ഞങ്ങൾക്ക് ലഭിക്കുമ്പോൾ, അതിന്റെ ആഴം ഞങ്ങൾ നൽകുന്നു.

അൽഗോരിതം

  1. റൂട്ട് ആണെങ്കിൽ NULL, മടങ്ങുക 0
  2. ട്രീ നോഡുകളുടെയും സംഖ്യകളുടെയും ജോഡി ക്യൂ സമാരംഭിക്കുക
  3. റൂട്ട് നോഡ് അതിന്റെ ആഴത്തിൽ ക്യൂവിലേക്ക് നീക്കുക 1
  4. ക്യൂ ശൂന്യമല്ലെങ്കിലും:
    • ഫ്രണ്ട് ക്യൂ എലമെന്റിന്റെ ഡെപ്ത്, നോഡ് വിലാസം വീണ്ടെടുക്കുക
    • ക്യൂവിൽ നിന്ന് ഒരു ഇനം പോപ്പ് ചെയ്യുക
    • ഫ്രണ്ട് നോഡ് ആണെങ്കിൽ NULL, അതിന്റെ ആഴം നൽകുക
    • പുഷ് ഇടത്തെ ഒപ്പം വലത് മരമുണ്ടെങ്കിൽ അവയിലേക്കുള്ള നോഡുകൾ അല്ല ശൂന്യം
  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

ബൈനറി ട്രീ ലീറ്റ്കോഡ് പരിഹാരത്തിന്റെ ഏറ്റവും കുറഞ്ഞ ആഴത്തിന്റെ സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (N), ഞങ്ങൾ വീണ്ടും വൃക്ഷം മുഴുവൻ സഞ്ചരിക്കുമ്പോൾ.

സ്ഥല സങ്കീർണ്ണത

O (N), ഓരോ നോഡിന്റെയും വിശദാംശങ്ങൾ സംഭരിക്കാൻ ഞങ്ങൾ ഒരു ക്യൂ ഉപയോഗിക്കുന്നതിനാൽ.