ಬೈನರಿ ಟ್ರೀ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದ ಕನಿಷ್ಠ ಆಳ


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಮೆಜಾನ್ ಆಪಲ್ ಫೇಸ್ಬುಕ್
ಬೈನರಿ ಟ್ರೀ ಅಗಲ ಮೊದಲ ಹುಡುಕಾಟ ಆಳದ ಮೊದಲ ಹುಡುಕಾಟ

ಈ ಸಮಸ್ಯೆಯಲ್ಲಿ, ಕೊಟ್ಟಿರುವ ಮೂಲದಿಂದ ಯಾವುದೇ ಎಲೆಯವರೆಗಿನ ಕಡಿಮೆ ಹಾದಿಯ ಉದ್ದವನ್ನು ನಾವು ಕಂಡುಹಿಡಿಯಬೇಕು ಬೈನರಿ ಮರ. ಇಲ್ಲಿ “ಮಾರ್ಗದ ಉದ್ದ” ಎಂದರೆ ಮೂಲ ನೋಡ್‌ನಿಂದ ಎಲೆ ನೋಡ್‌ಗೆ ನೋಡ್‌ಗಳ ಸಂಖ್ಯೆ. ಈ ಉದ್ದವನ್ನು ಬೈನರಿ ಮರದ ಕನಿಷ್ಠ ಆಳ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ.

ಉದಾಹರಣೆ

ಇನ್ಪುಟ್

ಬೈನರಿ ಟ್ರೀ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದ ಕನಿಷ್ಠ ಆಳ

 

 

 

 

 

 

 

2

ವಿವರಣೆ

ಕಡಿಮೆ ಮಾರ್ಗವೆಂದರೆ: 2 -> 1 , ಇದು ಉದ್ದ 2 ಆಗಿದೆ

ಇನ್ಪುಟ್

 

 

 

 

 

 

 

3

ವಿವರಣೆ

ಕಡಿಮೆ ಮಾರ್ಗವೆಂದರೆ: 1 -> 2 -> 3, ಉದ್ದ 3

ಅಪ್ರೋಚ್ (ಪುನರಾವರ್ತಿತ)

ಈ ಸಮಸ್ಯೆ ರಚನಾತ್ಮಕವಾಗಿ ಬೈನರಿ ಮರದ ಎತ್ತರವನ್ನು ಕಂಡುಹಿಡಿಯುವಂತೆಯೇ ಇರುತ್ತದೆ ಆದರೆ ಈ ಸಂದರ್ಭದಲ್ಲಿ, ನಾವು ಬೇರು ಮತ್ತು ಮರದ ಯಾವುದೇ ಎಲೆಯ ನಡುವಿನ ಕನಿಷ್ಠ ಎತ್ತರ / ಆಳವನ್ನು ಕಂಡುಹಿಡಿಯಬೇಕು. ನಾವು ಮೂಲದ ಎಡ ಮತ್ತು ಬಲ ಸಬ್‌ಟ್ರೀಗಳ ಕನಿಷ್ಠ ಆಳವನ್ನು ಹಿಂಪಡೆಯಬಹುದು ಆಳದ ಮೊದಲ ಹುಡುಕಾಟ (ಡಿಎಫ್‌ಎಸ್) ತದನಂತರ ಕನಿಷ್ಠ ಎರಡು ಆಳಗಳನ್ನು ಹಿಂತಿರುಗಿ. ನೋಡ್ನ ಎಡ ಮತ್ತು ಬಲ ಸಬ್ಟ್ರೀಗಳಲ್ಲಿ ಯಾವುದಾದರೂ ಇದ್ದಾಗ ನಾವು ಕೆಲವು ಪ್ರಕರಣಗಳನ್ನು ಪರಿಗಣಿಸಬೇಕಾಗಿದೆ ಸಾಂಕೇತಿಕಕೊಂಡಿಯು. ಎಡ ಸಬ್ಟ್ರೀ ಇದ್ದರೆ ಸೊನ್ನೆ, ಅದು ಸಮಾನ ಎತ್ತರವನ್ನು ಹಿಂದಿರುಗಿಸುತ್ತದೆ ಆದರೆ ಈ ಸಬ್‌ಟ್ರೀನಲ್ಲಿ ನಾವು ಯಾವುದೇ ಎಲೆಯನ್ನು ಕಂಡುಕೊಂಡಿಲ್ಲ, ಆದ್ದರಿಂದ ಇದು ತಪ್ಪು ಉತ್ತರವಾಗಿರುತ್ತದೆ. ಆದ್ದರಿಂದ, ಪುನರಾವರ್ತಿತ ಕಾರ್ಯವನ್ನು ನೋಡ್ ಎಂದು ಕರೆಯುವಾಗ ಮಾತ್ರ ನಾವು ಕರೆಯಬೇಕಾಗುತ್ತದೆ ಅಲ್ಲ ಶೂನ್ಯ.

ಕ್ರಮಾವಳಿ

  1. ಕಾರ್ಯವನ್ನು ರಚಿಸಿ minDepth () ಹಾದುಹೋದ ಮೂಲದ ಕನಿಷ್ಠ ಆಳವನ್ನು ಹಿಂತಿರುಗಿಸಲು
  2. ಮೂಲ ಇದ್ದರೆ ಸಾಂಕೇತಿಕಕೊಂಡಿಯು, ಹಿಂತಿರುಗಿ 0
  3. ಎರಡೂ ಸಂದರ್ಭದಲ್ಲಿ ಬಿಟ್ಟು ಮತ್ತು ಬಲ ಸಬ್ಟ್ರೀಗಳು ಸಾಂಕೇತಿಕಕೊಂಡಿಯು, ಹಿಂತಿರುಗಿ 1
  4. ಎಡ ಸಬ್ಟ್ರೀ ಇದ್ದರೆ ಸಾಂಕೇತಿಕಕೊಂಡಿಯು, ಹಿಂತಿರುಗಿ 1 + minDepth (ಮೂಲ-> ಬಲ)
  5. ಸರಿಯಾದ ಸಬ್‌ಟ್ರೀ ಇದ್ದರೆ ಬೇರೆ ಸಾಂಕೇತಿಕಕೊಂಡಿಯು, ಹಿಂತಿರುಗಿ 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

ಬೈನರಿ ಟ್ರೀ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದ ಕನಿಷ್ಠ ಆಳದ ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್), ನಾವು ಇಡೀ ಮರವನ್ನು ಒಮ್ಮೆ ಕೆಟ್ಟ ಸ್ಥಿತಿಯಲ್ಲಿ ಸಾಗಿಸಿದಾಗ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್). ಬೈನರಿ ಮರವನ್ನು ಓರೆಯಾಗಿಸಿದಾಗ, ಪುನರಾವರ್ತಿತ ಸ್ಟಾಕ್ ಚೌಕಟ್ಟುಗಳು ಒ (ಎನ್) ಜಾಗವನ್ನು ಸೇವಿಸಬಹುದು.

ಅಪ್ರೋಚ್ (ಪುನರಾವರ್ತನೆ)

ನಾವು ಬಳಸಬಹುದು ಅಗಲ-ಮೊದಲ ಹುಡುಕಾಟ (ಬಿಎಫ್‌ಎಸ್) ಎಲೆಯ ಮೊದಲ ನೋಡ್ ಅನ್ನು ಕಂಡುಹಿಡಿಯಲು ಮತ್ತು ಅದರ ಆಳವನ್ನು ಮೂಲದಿಂದ ಹಿಂತಿರುಗಿಸಲು. ಮೂಲ ನೋಡ್‌ನಿಂದ ಒಂದು ಜೋಡಿ ನೋಡ್‌ಗಳನ್ನು ಮತ್ತು ಅವುಗಳ ಆಳವನ್ನು ಸಂಗ್ರಹಿಸಲು ನಾವು ಕ್ಯೂ ಬಳಸಬಹುದು. ನಾವು ಎಲೆಯಾಗಿರುವ ನೋಡ್ ಅನ್ನು ಸ್ವೀಕರಿಸಿದಂತೆ, ನಾವು ಅದರ ಆಳವನ್ನು ಹಿಂದಿರುಗಿಸುತ್ತೇವೆ.

ಕ್ರಮಾವಳಿ

  1. ಮೂಲ ಇದ್ದರೆ ಸಾಂಕೇತಿಕಕೊಂಡಿಯು, ಹಿಂತಿರುಗಿ 0
  2. ಮರದ ನೋಡ್ಗಳು ಮತ್ತು ಪೂರ್ಣಾಂಕಗಳ ಜೋಡಿ ಕ್ಯೂ ಅನ್ನು ಪ್ರಾರಂಭಿಸಿ
  3. ರೂಟ್ ನೋಡ್ ಅನ್ನು ಅದರ ಆಳದೊಂದಿಗೆ ಕ್ಯೂಗೆ ತಳ್ಳಿರಿ 1
  4. ಕ್ಯೂ ಖಾಲಿಯಾಗಿಲ್ಲದಿದ್ದರೂ:
    • ಮುಂಭಾಗದ ಕ್ಯೂ ಅಂಶದ ಆಳ ಮತ್ತು ನೋಡ್ ವಿಳಾಸವನ್ನು ಹಿಂಪಡೆಯಿರಿ
    • ಸರದಿಯಿಂದ ಐಟಂ ಅನ್ನು ಪಾಪ್ ಮಾಡಿ
    • ಮುಂಭಾಗದ ನೋಡ್ ಇದ್ದರೆ ಸಾಂಕೇತಿಕಕೊಂಡಿಯು, ಅದರ ಆಳವನ್ನು ಹಿಂತಿರುಗಿ
    • ತಳ್ಳಿರಿ ಬಿಟ್ಟು ಮತ್ತು ಬಲ ಅವು ಇದ್ದರೆ ಮರಕ್ಕೆ ನೋಡ್‌ಗಳು ಅಲ್ಲ ಶೂನ್ಯ
  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

ಬೈನರಿ ಟ್ರೀ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದ ಕನಿಷ್ಠ ಆಳದ ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್), ನಾವು ಇಡೀ ಮರವನ್ನು ಮತ್ತೊಮ್ಮೆ ಹಾದುಹೋಗುವಾಗ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್), ಪ್ರತಿ ನೋಡ್‌ನ ವಿವರಗಳನ್ನು ಸಂಗ್ರಹಿಸಲು ನಾವು ಕ್ಯೂ ಬಳಸುತ್ತಿದ್ದಂತೆ.