N-ary သစ် Leetcode ဖြေရှင်းချက်၏အမြင့်ဆုံးအနက်


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် အမေဇုံ Google Microsoft က
အနံပထမရှာဖွေရေး အနက်ရောင်ပထမရှာဖွေမှု N-ary- သစ်ပင်

ဒီပြproblemနာမှာငါတို့ကိုပေးထားတယ် N-ary သစ်ပင်node များကိုကလေး ၂ ယောက်ထက် ပို၍ ခွင့်ပြုသည့်သစ်ပင်တစ်ပင်ဖြစ်သည်။ သစ်ပင်၏အမြစ်နှင့်အဝေးဆုံးသောအရွက်၏အတိမ်အနက်ကိုကျွန်ုပ်တို့ရှာဖွေရန်လိုအပ်သည်။ ၎င်းကိုအမြင့်ဆုံးအကျဆုံးဟုခေါ်သည်။ လမ်းကြောင်း၏အတိမ်အနက်သည်၎င်းပေါ်တွင်ရှိ node များအရေအတွက်ကိုသတိပြုပါ။

နမူနာ

       2

  /    |    \

3      4      6

                \
           
                  9
3

ရှင်းလင်းချက်: တန်ဖိုး ၉ ရှိသည့်အရွက်သည်အမြစ်မှအဝေးဆုံးနှင့်အနက်ဆုံးဖြစ်သည် 3။ ဒါကြောင့် ၃ ကိုထုတ်တယ်။

      2
  
  /      \

3           6   

        /   |   \

      4     7     9
3

ရှင်းလင်းချက်နံပါတ် ၄၊၇ နှင့် ၉ ရှိသောအရွက်များသည်အမြစ်မှအဝေးဆုံးနှင့်အနက်ဆုံးဖြစ်သည် 3။ ဒါကြောင့် ၃ ကိုထုတ်တယ်။

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

binary tree ၏အတိမ်အနက်ကိုမည်သည့် node မှမဆိုဘယ်ဘက်နှင့်ညာကလေးများအား recursive function ကိုခေါ်ခြင်းဖြင့်တွက်ချက်သည်။ အလားတူစွာ N-ary tree တစ်ခုတွင်အမြင့်ဆုံးအနက်ကိုမည်သည့် node မှမဆိုကလေးများအား recursive function ကိုခေါ်ခြင်းဖြင့်ကျွန်ုပ်တို့တွက်နိုင်သည်။ ဤချဉ်းကပ်မှုသည်ပြန်လည်ထူထောင်ခြင်းဖြစ်ပြီးသစ်ပင်တစ်ပင်တည်းကိုသာလိုအပ်သည်။

N-ary သစ် Leetcode ဖြေရှင်းချက်၏အမြင့်ဆုံးအနက်

algorithm

  1. function တစ်ခုဖန်တီးပါ maxDepth () အဘယ်သူ၏သစ်ပင်၏အမြင့်ဆုံးအတိမ်အနက်ကိုပြန်သွားဖို့ အမြစ် အဲဒါကိုကူးယူလိုက်ပြီ
  2. If အမြစ် တရားမဝင်သော
    • 0 ကိုပြန်သွားပါ
  3. တစ် ဦး variable ကို Initialize အမြင့်ဆုံး N-ary သစ်ပင်၏အမြင့်ဆုံးအတိမ်အနက်ကိုသိုလှောင်ရန်
  4. တိုင်းအတွက် ကလေး လက်ရှိအမြစ်၏သားသမီးစာရင်းတွင်:
    • အစုံ maximumDepth = max (maxDepth (root.left), maxDepth (root.right))
  5. ပြန်လာ maximumDepth + 1

N-ary သစ် Leetcode ဖြေရှင်းချက်၏အမြင့်ဆုံးအနက်ကိုအကောင်အထည်ဖော်ခြင်း

C ++ အစီအစဉ်

#include <bits/stdc++.h>
using namespace std;

struct Node
{
    int value;
    vector <Node*> children;

    Node(int val)
    {
        value = val;
        children = {};
    }

    Node(int val , vector <Node*> childList)
    {
        value = val;
        children = childList;
    }
};

int maxDepth(Node* root)
{
    if(root == NULL)
        return 0;
    int maximumDepth = 0;
    for(Node* &child : root->children)
        maximumDepth = max(maximumDepth , maxDepth(child));
    return maximumDepth + 1;
}

int main()
{
    Node* root = new Node(2);
    root->children = {new Node(3) , new Node(4) , new Node(5)};
    root->children[2]->children = {new Node(9)};
    cout << maxDepth(root) << '\n';
    return 0;
}

Java အစီအစဉ်

import java.lang.Math;

class Node
{
    int value;
    Node[] children;

    Node(int val)
    {
        value = val;
        children = new Node[]{};
    }

    Node(int val , Node[] childList)
    {
        value = val;
        children = childList;
    }
};

class maximum_depth
{
    public static void main(String args[])
    {
        Node root = new Node(2);
        Node[] a = {new Node(3) , new Node(4) , new Node(5)};
        root.children = a;
        Node[] b = {new Node(9)};
        root.children[2].children = b;
        System.out.println(maxDepth(root));
    }

    static int maxDepth(Node root)
    {
        if(root == null)
            return 0;
        int maximumDepth = 0;
        for(int i = 0 ; i < root.children.length ; i++)
            maximumDepth = Math.max(maximumDepth , maxDepth(root.children[i]));
        return maximumDepth + 1;
    }
}
3

N-ary သစ် Leetcode ဖြေရှင်းချက်၏အမြင့်ဆုံးအနက်ရှုပ်ထွေးမှုအားသုံးသပ်ခြင်း

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

အို (N)၊ = N-ary သစ်ပင်၏အရွယ်အစားသည်တစ်ချိန်ကသစ်ပင်တစ်ပင်ကိုကျွန်ုပ်တို့ဖြတ်သန်းသွားသည်။

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

အို (N) ကျွန်တော်တို့ဟာ recursive ခေါ်ဆိုမှုများအတွက်မှတ်ဉာဏ်ထဲမှာ stack frames များကိုသိုလှောင်အဖြစ်။

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

အထက်ပါလုပ်ငန်းစဉ်ကို node များနှင့်သူတို့၏နက်နဲသောရင်းမြစ်များကို root မှသိမ်းဆည်းရန် stack (သို့) တန်းစီတစ်ခုခုကိုသုံးခြင်းအားဖြင့်ထပ်မံပြုလုပ်နိုင်သည်။ အမြင့်ဆုံးအတိမ်အနက်သည်ဤလုပ်ငန်းစဉ်မှရရှိသောအမြစ်များအနက်အများဆုံးအနက်ဖြစ်သည်။ ဤရည်ရွယ်ချက်အတွက်ကျွန်ုပ်တို့သည် Queue ကိုအသုံးပြုသည်။ သစ်ပင်၏ element အားလုံးကိုအမြစ်မှနက်နဲသောအရာနှင့်အတူ Queue ထဲသို့တွန်းပို့သည်။ node တိုင်း၏အတိမ်အနက်ကိုအမြင့်ဆုံးနှင့်နှိုင်းယှဉ်ပြီးအသစ်ပြောင်းသည်။

algorithm

  1. function ကိုဖန်တီးပါ maxDepth () အထက်ပါချဉ်းကပ်မှုထဲမှာဆွေးနွေးထားတဲ့အတိုင်းဆင်တူသည်
  2. If အမြစ် is တရားမဝင်သော
    • 0 ကိုပြန်သွားပါ
  3. ကန ဦး အမြင့်ဆုံး ကျွန်တော်တို့ရဲ့ရလဒ်သိုလှောင်ရန်
  4. လူတန်းတန်းတစ်ခုကိုစတင်ပါ ဒြပ်စင် သစ်ပင် node များနှင့်၎င်းတို့၏နက်ရှိုင်းသောပါရှိသည်
  5. တွန်းထိုး အမြစ် နှင့်၎င်း၏အတိမ်အနက်ကို 1 အဖြစ်တန်းသို့
  6. စဉ် ဒြပ်စင် ဗလာမဟုတ်ပါ။
    • ရှေ့ node နှင့်၎င်း၏အမြင့်ကိုရယူပါ frontNode နှင့် မင်္ဂလာပါ
    • ပစ္စည်းကိုလူတန်းထဲမှထုတ်ပါ
    • If မင်္ဂလာပါ is သာ. ကြီး ထက် အမြင့်ဆုံး
      1. Update ကို maximumDepth = frontNodeDepth
    • If frontNode is တရားမဝင်သော
      1. နက်နက်နဲနဲနက်နက်ရှိုင်းရှိုင်းနှင့်အတူ၎င်း၏ကလေးများအားလုံးတန်းစီသို့တွန်းအားပေး မင်္ဂလာပါ + 1
  7. ပြန်လာ အမြင့်ဆုံး
  8. ရလဒ်ပုံနှိပ်ပါ

N-ary သစ် Leetcode ဖြေရှင်းချက်၏အမြင့်ဆုံးအနက်ကိုအကောင်အထည်ဖော်ခြင်း

C ++ အစီအစဉ်

#include <bits/stdc++.h>
using namespace std;

struct Node
{
    int value;
    vector <Node*> children;

    Node(int val)
    {
        value = val;
        children = {};
    }

    Node(int val , vector <Node*> childList)
    {
        value = val;
        children = childList;
    }
};

int maxDepth(Node* root)
{
    if(root == NULL)
        return 0;
    int maximumDepth = 0 , frontNodeDepth;

    queue <pair <Node* , int> > elements;
    elements.push({root , 1});
    Node* frontNode;
    while(!elements.empty())
    {
        frontNode = elements.front().first;
        frontNodeDepth = elements.front().second;
        elements.pop();
        if(frontNodeDepth > maximumDepth)
            maximumDepth = frontNodeDepth;

        if(frontNode != NULL)
        {
            for(Node* &child : frontNode->children)
                elements.push({child , frontNodeDepth + 1});
        }
    }

    return maximumDepth;
}

int main()
{
    Node* root = new Node(2);
    root->children = {new Node(3) , new Node(4) , new Node(5)};
    root->children[2]->children = {new Node(9)};
    cout << maxDepth(root) << '\n';
    return 0;
}

Java အစီအစဉ်

import java.lang.Math;
import java.util.*;

class Node
{
    int value;
    Node[] children;

    Node(int val)
    {
        value = val;
        children = new Node[]{};
    }

    Node(int val , Node[] childList)
    {
        value = val;
        children = childList;
    }
};

class Pair
{
    Node key;
    int value;
    Pair(Node root , int val)
    {
        key = root;
        value = val;
    }
}

class maximum_depth
{
    public static void main(String args[])
    {
        Node root = new Node(2);
        Node[] a = {new Node(3) , new Node(4) , new Node(5)};
        root.children = a;
        Node[] b = {new Node(9)};
        root.children[2].children = b;
        System.out.println(maxDepth(root));
    }

    static int maxDepth(Node root)
    {
        if(root == null)
            return 0;
        LinkedList <Pair> elements = new LinkedList <>();
        elements.add(new Pair(root , 1));
        Node frontNode;
        int maximumDepth = 0 , frontNodeDepth;

        while(elements.size() > 0)
        {
            frontNode = elements.peek().key;
            frontNodeDepth = elements.peek().value;
            elements.remove();
            if(frontNodeDepth > maximumDepth)
                maximumDepth = frontNodeDepth;

            if(frontNode != null)
            {
                for(int i = 0 ; i < frontNode.children.length ; i++)
                    elements.add(new Pair(frontNode.children[i] , frontNodeDepth + 1));
            }
        }
        return maximumDepth;
    }
}
3

N-ary သစ် Leetcode ဖြေရှင်းချက်၏အမြင့်ဆုံးအနက်ရှုပ်ထွေးမှုအားသုံးသပ်ခြင်း

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

အို (N) ကျနော်တို့နောက်တဖန်တပြင်လုံးကိုသစ်ပင်ဖြတ်သန်းအဖြစ်။ N ကို = သစ်ပင်၏အရွယ်အစား

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

အို (N) ကျနော်တို့နက်ရှိုင်းနှင့်အတူသစ်ပင်၌ရှိသမျှသော node များသိုလှောင်ရန်တန်းစီကိုအသုံးပြုသည်။