የሁለትዮሽ ዛፍ Leetcode መፍትሔ አነስተኛ ጥልቀት


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን ፓም ፌስቡክ
ሁለትዮሽ ዛፍ ስፌት የመጀመሪያ ፍለጋ ጥልቀት የመጀመሪያ ፍለጋ

በዚህ ችግር ውስጥ ፣ በተሰጠው ውስጥ ከሥሩ ጀምሮ እስከ ማናቸውም ቅጠል ድረስ ያለውን አጭሩ ጎዳና ርዝመት መፈለግ አለብን ሁለትዮሽ ዛፍ. እዚህ ላይ “የመንገዱ ርዝመት” ማለት ከሥሩ መስቀለኛ መንገድ እስከ ቅጠሉ መስቀለኛ ክፍል ድረስ የአንጓዎች ብዛት ማለት መሆኑን ልብ ይበሉ። ይህ ርዝመት የአንድ ሁለትዮሽ ዛፍ አነስተኛ ጥልቀት ተብሎ ይጠራል።

ለምሳሌ

ግቤት

የሁለትዮሽ ዛፍ Leetcode መፍትሔ አነስተኛ ጥልቀት

 

 

 

 

 

 

 

2

ማስረጃ

በጣም አጭሩ መንገድ 2 -> 1 , እሱም ርዝመቱ 2 ነው

ግቤት

 

 

 

 

 

 

 

3

ማስረጃ

አጭሩ መንገድ 1 -> 2 -> 3፣ ርዝመት 3

አቀራረብ (ተደጋጋሚ)

ይህ ችግር በመዋቅራዊ ደረጃ የሁለትዮሽ ዛፍ ቁመት ከማግኘት ጋር ተመሳሳይ ነው ነገር ግን በዚህ ጉዳይ ላይ ሥሩ እና በዛፉ ውስጥ ባለው ማንኛውም ቅጠል መካከል ያለውን ዝቅተኛ ቁመት / ጥልቀት መፈለግ አለብን ፡፡ በመጠቀም የግራ እና የቀኝ ንዑስ ቁጥሮችን ዝቅተኛ ጥልቀት መውሰድ እንችላለን ጥልቀት የመጀመሪያ ፍለጋ (DFS) እና ከዚያ የሁለቱን ጥልቀቶች ዝቅ ያድርጉ ፡፡ የመስቀለኛ ክፍል የግራ እና የቀኝ ንዑስ ክፍሎች ሲሆኑ አንዳንድ ጉዳዮችን ከግምት ውስጥ ማስገባት አለብን ባዶ. የግራ ንዑስ ዛፍ ከሆነ ሙሉ ፣ እሱ እኩል የሆነ ቁመት ይመልሳል ግን በዚህ ንዑስ ክፍል ውስጥ ምንም ቅጠል እንዳላገኘነው እንዲሁ ነው የሚል የተሳሳተ መልስ ይሆናል ፡፡ ስለሆነም ፣ ተሃድሶውን መጥራት ያለብን የተጠራው መስቀለኛ መንገድ ሲኖር ብቻ ነው አይደለም ከንቱ

አልጎሪዝም

  1. ተግባር ይፍጠሩ ደቂቃ ጥልቀት () የተላለፈውን ሥር ዝቅተኛውን ጥልቀት ለመመለስ
  2. ሥሩ ከሆነ ባዶ፣ ተመለስ 0
  3. ሁለቱም ቢሆኑ ግራቀኝ ንዑስ ዛፎች ናቸው ባዶ፣ መመለስ 1
  4. የግራ ንዑስ ዛፍ ከሆነ ባዶ፣ ተመለስ 1 + ደቂቃ ጥልቀት (root-> ቀኝ)
  5. ካልሆነ ጉዳዩ ትክክለኛ ንዑስ ዛፍ ከሆነ ባዶ፣ ተመለስ 1 + ደቂቃ ጥልቀት (root-> ግራ)
  6. መመለስ 1 + ዝቅተኛ (ደቂቃ ጥልቀት(root-> ግራ) ፣ ደቂቃ ጥልቀት(ሥር-> ቀኝ))

የሁለትዮሽ ዛፍ ሌትኮድ መፍትሔ አነስተኛ ጥልቀት ትግበራ

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

የሁለትዮሽ ዛፍ ሌትኮድ መፍትሔ ጥቃቅን ጥልቀት ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (ኤን)፣ በጣም በከፋ ሁኔታ ውስጥ እንኳን አንድ ጊዜ መላውን ዛፍ ስናቋርጥ ፡፡

የቦታ ውስብስብነት

ኦ (ኤን) የሁለትዮሽ ዛፍ ሲዛባ ፣ ተደጋጋሚ የቁልል ክፈፎች እስከ ኦ (ኤን) ቦታ ድረስ ሊፈጁ ይችላሉ።

አቀራረብ (ኢተራዊ)

መጠቀም እንችላለን ስፌት-የመጀመሪያ ፍለጋ (ቢኤፍኤስ) ቅጠል የሆነውን የመጀመሪያውን መስቀለኛ መንገድ ለማግኘት እና ጥልቀቱን ከሥሩ ይመልሱ ፡፡ ጥንድ አንጓዎችን እና ጥልቀታቸውን ከሥሩ መስቀለኛ ክፍል ለማከማቸት ወረፋ መጠቀም እንችላለን ፡፡ ቅጠል የሆነውን መስቀለኛ ክፍል ስንቀበል ጥልቀቱን እንመልሳለን ፡፡

አልጎሪዝም

  1. ሥሩ ከሆነ ባዶ፣ ተመለስ 0
  2. ጥንድ የዛፍ አንጓዎች እና የቁጥር ቁጥሮች ወረፋ ያስጀምሩ
  3. የስር መስቀለኛ መንገዱን ከጥልቀት ጋር ወደ ወረፋው ይግፉት 1
  4. ወረፋው ባዶ ባይሆንም
    • የፊት ወረፋውን ጥልቀት እና የመስቀለኛ ክፍል አድራሻ ሰርስረው ያውጡ
    • ከወረፋው ውስጥ አንድ ንጥል ብቅ ያድርጉ
    • የፊት መስቀለኛ መንገድ ከሆነ ባዶ, ጥልቀቱን ይመልሱ
    • ግፋ ግራቀኝ ከሆኑ ለዛፉ አንጓዎች አይደለም ባዶ
  5. ተመለስ -1 ተግባሩ ኢንቲጀር ስለሚመልስ የፕሮግራሙን አገባብ ለማስጠበቅ

የሁለትዮሽ ዛፍ ሌትኮድ መፍትሔ አነስተኛ ጥልቀት ትግበራ

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

የሁለትዮሽ ዛፍ ሌትኮድ መፍትሔ ጥቃቅን ጥልቀት ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (ኤን)እንደገና መላውን ዛፍ ስናልፍ ፡፡

የቦታ ውስብስብነት

ኦ (ኤን)፣ የእያንዳንዱ መስቀለኛ መንገድ ዝርዝሮችን ለማከማቸት ወረፋ እንደምንጠቀም ፡፡