ਬਾਈਨਰੀ ਟਰੀ ਲੀਟਕੋਡ ਘੋਲ ਦੀ ਘੱਟੋ ਘੱਟ ਡੂੰਘਾਈ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਸੌਖੀ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਐਮਾਜ਼ਾਨ ਸੇਬ ਫੇਸਬੁੱਕ
ਬਾਈਨਰੀ ਟਰੀ ਚੌੜਾਈ ਪਹਿਲੀ ਖੋਜ ਡੂੰਘਾਈ ਪਹਿਲੀ ਖੋਜ

ਇਸ ਸਮੱਸਿਆ ਵਿੱਚ, ਸਾਨੂੰ ਇੱਕ ਦਿੱਤੇ ਵਿੱਚ ਜੜ੍ਹ ਤੋਂ ਕਿਸੇ ਪੱਤੇ ਤੱਕ ਦੇ ਛੋਟੇ ਮਾਰਗ ਦੀ ਲੰਬਾਈ ਨੂੰ ਲੱਭਣ ਦੀ ਜ਼ਰੂਰਤ ਹੈ ਬਾਈਨਰੀ ਟਰੀ. ਯਾਦ ਰੱਖੋ ਕਿ ਇੱਥੇ “ਮਾਰਗ ਦੀ ਲੰਬਾਈ” ਦਾ ਅਰਥ ਹੈ ਰੂਟ ਨੋਡ ਤੋਂ ਪੱਤਾ ਨੋਡ ਤੱਕ ਨੋਡਾਂ ਦੀ ਗਿਣਤੀ. ਇਸ ਲੰਬਾਈ ਨੂੰ ਇੱਕ ਬਾਈਨਰੀ ਟਰੀ ਦੀ ਘੱਟੋ ਘੱਟ ਡੂੰਘਾਈ ਕਿਹਾ ਜਾਂਦਾ ਹੈ.

ਉਦਾਹਰਨ

ਇੰਪੁੱਟ

ਬਾਈਨਰੀ ਟਰੀ ਲੀਟਕੋਡ ਘੋਲ ਦੀ ਘੱਟੋ ਘੱਟ ਡੂੰਘਾਈ

 

 

 

 

 

 

 

2

ਕਥਾ

ਸਭ ਤੋਂ ਛੋਟਾ ਮਾਰਗ ਇਹ ਹੈ: 2 -> 1 , ਜਿਸਦੀ ਲੰਬਾਈ 2 ਹੈ

ਇੰਪੁੱਟ

 

 

 

 

 

 

 

3

ਕਥਾ

ਸਭ ਤੋਂ ਛੋਟਾ ਮਾਰਗ ਇਹ ਹੈ: 1 -> 2 -> 3, ਲੰਬਾਈ 3

ਪਹੁੰਚ (ਰਿਕਰਸਿਵ)

ਇਹ ਸਮੱਸਿਆ inaryਾਂਚਾਗਤ ਤੌਰ ਤੇ ਇਕ ਬਾਈਨਰੀ ਰੁੱਖ ਦੀ ਉਚਾਈ ਲੱਭਣ ਦੇ ਸਮਾਨ ਹੈ ਪਰ ਇਸ ਸਥਿਤੀ ਵਿਚ, ਸਾਨੂੰ ਦਰੱਖਤ ਵਿਚਲੀ ਜੜ ਅਤੇ ਕਿਸੇ ਪੱਤੇ ਦੇ ਵਿਚਕਾਰ ਘੱਟੋ ਘੱਟ ਉਚਾਈ / ਡੂੰਘਾਈ ਲੱਭਣ ਦੀ ਜ਼ਰੂਰਤ ਹੈ. ਅਸੀਂ ਰੂਟ ਦੇ ਖੱਬੇ ਅਤੇ ਸੱਜੇ ਉਪ-ਟ੍ਰੀਸ ਦੀ ਘੱਟੋ ਘੱਟ ਡੂੰਘਾਈ ਪ੍ਰਾਪਤ ਕਰ ਸਕਦੇ ਹਾਂ ਡੂੰਘਾਈ ਪਹਿਲੀ ਖੋਜ (ਡੀ.ਐੱਫ.ਐੱਸ.) ਅਤੇ ਫਿਰ ਘੱਟੋ ਘੱਟ ਦੋ ਡੂੰਘਾਈਆਂ ਨੂੰ ਵਾਪਸ ਕਰੋ. ਸਾਨੂੰ ਕੁਝ ਮਾਮਲਿਆਂ 'ਤੇ ਵਿਚਾਰ ਕਰਨ ਦੀ ਜ਼ਰੂਰਤ ਹੈ ਜਦੋਂ ਕਿਸੇ ਨੋਡ ਦੇ ਖੱਬੇ ਅਤੇ ਸੱਜੇ ਉਪ-ਟ੍ਰੀਸ ਹੁੰਦੇ ਹਨ NULL. ਜੇ ਖੱਬਾ ਸਬਟ੍ਰੀ ਹੈ NULL, ਇਹ ਇਕ ਉਚਾਈ ਦੇ ਬਰਾਬਰ ਵਾਪਸ ਆਵੇਗਾ ਪਰ ਜਿਵੇਂ ਕਿ ਸਾਨੂੰ ਇਸ ਉਪਸਰੀ ਵਿਚ ਕੋਈ ਪੱਤਾ ਨਹੀਂ ਮਿਲਿਆ, ਇਸ ਲਈ ਇਹ ਇੱਕ ਗਲਤ ਜਵਾਬ ਹੋਵੇਗਾ. ਇਸ ਲਈ, ਸਾਨੂੰ ਸਿਰਫ ਉਦੋਂ ਵਾਪਸੀ ਫੰਕਸ਼ਨ ਨੂੰ ਕਾਲ ਕਰਨ ਦੀ ਜ਼ਰੂਰਤ ਹੁੰਦੀ ਹੈ ਜਦੋਂ ਨੋਡ ਜਿਸ ਤੇ ਇਸਨੂੰ ਬੁਲਾਇਆ ਜਾਂਦਾ ਹੈ ਨਾ ਖਾਲੀ

ਐਲਗੋਰਿਥਮ

  1. ਇੱਕ ਫੰਕਸ਼ਨ ਬਣਾਓ minDepth () ਪਾਸ ਕੀਤੀ ਰੂਟ ਦੀ ਘੱਟੋ ਘੱਟ ਡੂੰਘਾਈ ਨੂੰ ਵਾਪਸ ਕਰਨ ਲਈ
  2. ਜੇ ਰੂਟ ਹੈ NULL, ਵਾਪਸ 0
  3. ਕੇਸ ਵਿੱਚ ਦੋਨੋ ਨੂੰ ਛੱਡ ਅਤੇ ਸੱਜੇ ਟਾਇਟਰਸ ਹਨ NULLਵਾਪਸ, 1
  4. ਜੇ ਖੱਬਾ ਸਬਟ੍ਰੀ ਹੈ NULL, ਵਾਪਸ 1 + minDepth (ਰੂਟ-> ਸੱਜਾ)
  5. ਨਹੀਂ ਤਾਂ ਜੇ ਸਹੀ ਸਬਟ੍ਰੀ ਹੈ NULL, ਵਾਪਸ 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

ਬਾਈਨਰੀ ਟਰੀ ਲੀਟਕੋਡ ਘੋਲ ਦੀ ਘੱਟੋ ਘੱਟ ਡੂੰਘਾਈ ਦਾ ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਟਾਈਮ ਜਟਿਲਤਾ

ਓ (ਐਨ), ਜਿਵੇਂ ਕਿ ਅਸੀਂ ਇਕ ਵਾਰ ਵੀ ਸਭ ਤੋਂ ਬੁਰੀ ਸਥਿਤੀ ਵਿਚ ਪੂਰੇ ਰੁੱਖ ਨੂੰ ਪਾਰ ਕਰਦੇ ਹਾਂ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਓ (ਐਨ) ਜਦੋਂ ਬਾਈਨਰੀ ਰੁੱਖ ਸਕਿwed ਹੋ ਜਾਂਦਾ ਹੈ, ਲਗਾਤਾਰ ਹੋਣ ਵਾਲੇ ਸਟੈਕ ਫਰੇਮ O (N) ਸਪੇਸ ਤੱਕ ਦਾ ਸੇਵਨ ਕਰ ਸਕਦੇ ਹਨ.

ਪਹੁੰਚ (ਨਜ਼ਰਸਾਨੀ)

ਅਸੀਂ ਵਰਤ ਸਕਦੇ ਹਾਂ ਬਰੈਥਥ-ਫਸਟ ਸਰਚ (ਬੀ.ਐੱਫ.ਐੱਸ.) ਪਹਿਲਾ ਨੋਡ ਲੱਭਣ ਲਈ ਜੋ ਇਕ ਪੱਤਾ ਹੈ ਅਤੇ ਇਸ ਦੀ ਡੂੰਘਾਈ ਨੂੰ ਜੜ੍ਹ ਤੋਂ ਵਾਪਸ ਕਰਨਾ. ਅਸੀਂ ਨੋਡਾਂ ਦੀ ਇੱਕ ਜੋੜਾ ਅਤੇ ਰੂਟ ਨੋਡ ਤੋਂ ਉਨ੍ਹਾਂ ਦੀ ਡੂੰਘਾਈ ਨੂੰ ਸਟੋਰ ਕਰਨ ਲਈ ਕਤਾਰ ਦੀ ਵਰਤੋਂ ਕਰ ਸਕਦੇ ਹਾਂ. ਜਿਵੇਂ ਕਿ ਸਾਨੂੰ ਇੱਕ ਨੋਡ ਮਿਲਦਾ ਹੈ ਜੋ ਇੱਕ ਪੱਤਾ ਹੈ, ਅਸੀਂ ਇਸ ਦੀ ਡੂੰਘਾਈ ਨੂੰ ਵਾਪਸ ਕਰਦੇ ਹਾਂ.

ਐਲਗੋਰਿਥਮ

  1. ਜੇ ਰੂਟ ਹੈ NULL, ਵਾਪਸ 0
  2. ਟ੍ਰੀ ਨੋਡਜ਼ ਅਤੇ ਪੂਰਨ ਅੰਕ ਦੀ ਜੋੜੀ ਦੀ ਇੱਕ ਕਤਾਰ ਅਰੰਭ ਕਰੋ
  3. ਰੂਟ ਨੋਡ ਨੂੰ ਇਸ ਦੀ ਡੂੰਘਾਈ ਨਾਲ ਕਤਾਰ ਵਿੱਚ ਧੱਕੋ 1
  4. ਜਦੋਂ ਕਿ ਕਤਾਰ ਖਾਲੀ ਨਹੀਂ ਹੈ:
    • ਸਾਹਮਣੇ ਵਾਲੀ ਕਤਾਰ ਦੇ ਤੱਤ ਦੀ ਡੂੰਘਾਈ ਅਤੇ ਨੋਡ ਪਤਾ ਪ੍ਰਾਪਤ ਕਰੋ
    • ਇੱਕ ਵਸਤੂ ਨੂੰ ਕਤਾਰ ਤੋਂ ਬਾਹਰ ਕੱ Popੋ
    • ਜੇ ਸਾਹਮਣੇ ਨੋਡ ਹੈ NULL, ਇਸ ਦੀ ਡੂੰਘਾਈ ਵਾਪਸ
    • ਧੱਕੋ ਨੂੰ ਛੱਡ ਅਤੇ ਸੱਜੇ ਉਹ ਹਨ, ਜੇ ਰੁੱਖ ਨੂੰ ਹਿਲਾ ਨਾ 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

ਬਾਈਨਰੀ ਟਰੀ ਲੀਟਕੋਡ ਘੋਲ ਦੀ ਘੱਟੋ ਘੱਟ ਡੂੰਘਾਈ ਦਾ ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਟਾਈਮ ਜਟਿਲਤਾ

ਓ (ਐਨ), ਜਿਵੇਂ ਕਿ ਅਸੀਂ ਇਕ ਵਾਰ ਫਿਰ ਪੂਰੇ ਰੁੱਖ ਨੂੰ ਪਾਰ ਕਰਦੇ ਹਾਂ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਓ (ਐਨ), ਜਿਵੇਂ ਕਿ ਅਸੀਂ ਹਰ ਨੋਡ ਦੇ ਵੇਰਵਿਆਂ ਨੂੰ ਸਟੋਰ ਕਰਨ ਲਈ ਕਤਾਰ ਦੀ ਵਰਤੋਂ ਕਰਦੇ ਹਾਂ.