Binary Tree Leetcode Solution ၏အနည်းဆုံးအနက်


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် အမေဇုံ Apple Facebook က
ဒွိသစ်ပင် အနံပထမရှာဖွေရေး အနက်ရောင်ပထမရှာဖွေမှု

ဤပြproblemနာတွင်အမြစ်တိုမှမည်သည့်အရွက်သို့မဆိုအတိုဆုံးလမ်းကြောင်းအရှည်ကိုကျွန်ုပ်တို့ရှာဖွေရန်လိုအပ်သည် ဒွိသစ်ပင်။ သတိပြုရန်မှာဤတွင်ဖော်ပြထားသော“ လမ်းကြောင်းအရှည်” သည် root node မှ leaf node သို့ node များအရေအတွက်ကိုဆိုလိုသည်။ ဒီအရှည်ကို Binary Tree of Minimum Depth လို့ခေါ်တယ်။

နမူနာ

input

Binary Tree Leetcode Solution ၏အနည်းဆုံးအနက်

 

 

 

 

 

 

 

2

ရှင်းလင်းချက်

အတိုဆုံးလမ်းကြောင်းကတော့ 2 -> 1 , အရှည် 2 ဖြစ်သော

input

 

 

 

 

 

 

 

3

ရှင်းလင်းချက်

အတိုဆုံးလမ်းကြောင်းကတော့ 1 -> 2 -> 3အရှည် 3

ချဉ်းကပ်နည်း (Recursive)

ဤပြproblemနာသည်ဖွဲ့စည်းတည်ဆောက်ပုံနှင့်အတူတူ binary tree ၏အမြင့်ကိုရှာဖွေခြင်းနှင့်အတူတူပင်ဖြစ်သော်လည်းဤကိစ္စတွင်သစ်ပင်ရှိအမြစ်နှင့်မည်သည့်အရွက်များအကြားအနည်းဆုံးအမြင့် / အတိမ်အနက်ကိုကျွန်ုပ်တို့ရှာရန်လိုအပ်သည်။ ကျနော်တို့အသုံးပြုနေတဲ့အမြစ်ရဲ့ဘယ်ဘက်နဲ့ညာ subtrees တွေရဲ့အနိမ့်ဆုံးအနက်ကိုထုတ်ယူနိုင်ပါတယ် အနက်ရောင်ပထမရှာဖွေမှု (DFS) ထို့နောက်အနက်နှစ်ခုအနက်မှနိမ့်ဆုံးကိုပြန်သွားပါ။ node တစ်ခု၏ဘယ်ဘက်နှင့်ညာ subtrees နှစ်ခုစလုံးသည်ဖြစ်စဉ်အချို့ကိုကျွန်ုပ်တို့စဉ်းစားရန်လိုအပ်သည် null။ ဘယ်ဘက် subtree သည်ဆိုပါက null ညီမျှသောအမြင့်ကိုပြန်ပေးလိမ့်မည် ဒါပေမယ့်ကျနော်တို့ဒီ subtree ၌အရွက်မတွေ့ရသကဲ့သို့, ဒါ မှားယွင်းတဲ့အဖြေတစ်ခုဖြစ်လိမ့်မယ်။ ထို့ကြောင့် nour node ကိုခေါ်သောအခါ recursive function ကိုခေါ်ရန်သာလိုသည် တရားမဝင်

algorithm

  1. function တစ်ခုဖန်တီးပါ minDepth () လွန်အမြစ်၏နိမ့်ဆုံးအတိမ်အနက်ကိုပြန်သွားဖို့
  2. အမြစ်သည်ဆိုပါက nullပြန်လာ 0
  3. ကိစ္စတွင်နှစ် ဦး စလုံး လက်ဝဲဘက် နှင့် မှန်သော တော null, 1 ပြန်လာ
  4. ဘယ်ဘက် subtree သည်ဆိုပါက nullပြန်လာ ၁ + minDepth (root-> ညာ)
  5. အခြားကိစ္စရပ်မှန်လျှင်, လက်ျာ subtree ဖြစ်ပါတယ် nullပြန်လာ ၁ + minDepth (root-> ဘယ်ဘက်)
  6. ၁ + အနိမ့်ဆုံးသို့ပြန်သွားသည်။minDepth(root-> ဘယ်ဘက်), minDepth(root-> ညာ)

Binary Tree Leetcode Solution ၏အနည်းဆုံးအတိမ်အနက်ကိုအကောင်အထည်ဖော်ခြင်း

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';
}

Java အစီအစဉ်

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

Binary Tree Leetcode Solution ၏အနည်းဆုံးအနက်ကိုရှုပ်ထွေးစွာဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (N)ကျနော်တို့အဆိုးဆုံးကိစ္စများတွင်တစ်ချိန်ကသစ်ပင်တစ်ခုလုံးဖြတ်သန်းအဖြစ်။

အာကာသရှုပ်ထွေးမှု

အို (N) ။ binary သစ်ပင်ကို skewed သောအခါ, recursive stack frames များကို O (N) အာကာသ upto စားသုံးလိမ့်မည်။

ချဉ်းကပ်မှု (ကြားမှာ)

ကျနော်တို့ကိုသုံးနိုင်သည် အနံအလိုက်ရှာဖွေခြင်း (BFS) အရွက်တစ်ခုဖြစ်သောပထမဆုံး node ကိုရှာပြီးအမြစ်မှအနက်ပြန်ပေးရန်ဖြစ်သည်။ node တစ်ခုနှင့် ၄ င်းနက်နဲရာများကို root node မှသိမ်းဆည်းရန်ကျွန်ုပ်တို့သည် Queue တစ္ခုကိုသုံးနိုင်သည်။ အရွက်တစ်ခုဖြစ်သော node တစ်ခုကိုကျွန်ုပ်တို့ရရှိသည်နှင့်အမျှ၎င်းသည်၎င်း၏အနက်ကိုပြန်ပို့ပေးသည်။

algorithm

  1. အကယ်၍ root သည်ဆိုရင် nullပြန်လာ 0
  2. သစ်ပင် node များနှင့်ကိန်း၏စုံတွဲတစ်တွဲ၏တန်းစီ Initialize
  3. ၎င်းကိုနက်နက်နဲနဲနက်ရှိုင်းသည့်တန်းစီသို့ root node ကိုတွန်းပါ 1
  4. အဆိုပါတန်းစီအချည်းနှီးဖြစ်နေစဉ်:
    • ရှေ့တန်း element ရဲ့အတိမ်အနက်နှင့် node လိပ်စာကိုပြန်လည်ရယူပါ
    • ပစ္စည်းကိုလူတန်းထဲမှထုတ်ပါ
    • ရှေ့ node ကိုလျှင် null၎င်း၏အတိမ်အနက်ကိုပြန်သွားပါ
    • Push ကို လက်ဝဲဘက် နှင့် မှန်သော သူတို့ကလျှင်သစ်ပင်မှ node များ မဟုတ် တရားမဝင်သော
  5. ပြန်လာ -1 ပရိုဂရမ်၏ syntax ကိုဆက်လက်ထိန်းသိမ်းထားရန် function သည် integer တစ်ခုဖြစ်သည်

Binary Tree Leetcode Solution ၏အနည်းဆုံးအတိမ်အနက်ကိုအကောင်အထည်ဖော်ခြင်း

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';
}


Java အစီအစဉ်

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

Binary Tree Leetcode Solution ၏အနည်းဆုံးအနက်ကိုရှုပ်ထွေးစွာဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (N)ကျနော်တို့တခါသစ်ပင်တပြင်လုံးကိုဖြတ်သန်းအဖြစ်။

အာကာသရှုပ်ထွေးမှု

အို (N)node တိုင်း၏အသေးစိတ်အချက်အလက်များကိုသိမ်းဆည်းရန်၊