တစ် ဦး Binary သစ်ပင်၏အောက်ခြေမြင်ကွင်း


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် တိကျသော အမေဇုံ ကူပွန် Flipkart Paytm Walmart ဓာတ်ခွဲခန်းများ
ဒွိသစ်ပင် သစ်ပင် သစ်ပင်လှည့်လည်

ပြProbleနာဖော်ပြချက်

“ Binary Tree of Bottom View” ပြproblemနာကသင်အား binary tree ပေးပြီးယခုပေးထားသောအောက်ခြေမြင်ကွင်းကိုရှာဖွေရန်လိုအပ်သည်ဟုဖော်ပြသည် သစ်ပင်။ ကျနော်တို့အောက်ဖက် ဦး တည်ချက်ကနေအပင်တစ်ပင်ကိုမြင်သောအခါ။ ကျွန်တော်တို့ကိုမြင်နိုင်သော node များသည် binary tree ၏အောက်ခြေမြင်ကွင်းဖြစ်သည်။

နမူနာ

တစ် ဦး Binary သစ်ပင်၏အောက်ခြေမြင်ကွင်း

5 6 4 7

ချဉ်းကပ်နည်း

ချဉ်းကပ်နည်းသည်ရိုးရှင်းပါသည်၊ အဘယ်ကြောင့်ဆိုသော်ကျွန်ုပ်တို့သည်ဤကဲ့သို့သောပြaနာကိုကျွန်ုပ်တို့ဖြေရှင်းပြီးပါပြီ။ ပြproblemနာ binary tree အပေါ်မှမြင်ကွင်းသည်အထက်ပါလမ်းကြောင်းမှကျွန်ုပ်တို့မြင်နိုင်သော node များကို print ထုတ်ရသည့်နေရာနှင့်ဆင်တူသည်။ ဒီတော့ဒီပြsolveနာကိုဘယ်လိုဖြေရှင်းမလဲ။

ကျနော်တို့ဒီမှာအလျားလိုက်အကွာအဝေး၏အယူအဆကိုအသုံးပြုရန်လိုအပ်သည်။ node တစ်ခု၏ဘယ်ဘက်သို့ကျွန်ုပ်တို့ရွှေ့လိုက်တိုင်းလက်ရှိ node ၏အလျားလိုက်အကွာအဝေးမှနုတ်ပါ။ ထိုနည်းတူစွာကျွန်ုပ်တို့သည်မှန်ကန်သောလမ်းကြောင်းသို့ရွေ့လျှင် 1 ကိုအလျားလိုက်အကွာအဝေးသို့ပေါင်းထည့်သည်။ ပြီးတာနဲ့ကျွန်တော်ဒီအယူအဆနှင့်ရင်းနှီးကျွမ်းဝင်ကြသည်။ အလျားလိုက်အကွာအဝေးတစ်ခုစီတွင် node များကိုခြေရာခံရန်မြေပုံကိုကျွန်ုပ်တို့အသုံးပြုမည်။ ပြီးရင်သစ်ပင်ကိုဖြတ်ပြီးငါတို့ node ကိုရှာလိုက်တိုင်းငါတို့မြေပုံကို update လုပ်တယ်။ အလျားလိုက်အကွာအဝေးကိုသော့အဖြစ်ထားရှိမည်ဖြစ်ပြီး node သည်မြေပုံအတွက်တန်ဖိုးဖြစ်သည်။ ဒါကြောင့် level order traversal ကိုသုံးပြီးအလျားလိုက်အကွာအဝေးကိုတွက်ချက်ပြီး update ကိုဆက်လုပ်ပါ မြေပုံ.

ဤတွက်ချက်မှုများပြီးနောက်မြေပုံရှိအရာများကိုသာပုံနှိပ်ပါ။ ဘယ်ဘက်ဆုံး node သည်အနိမ့်ဆုံးအလျားလိုက်အကွာအဝေးနှင့်အတူရှိပြီးညာဘက် node သည်အမြင့်ဆုံးသောအကောင်းမြင်တန်ဖိုးရှိသောကြောင့်ဖြစ်သည်။

Binary Tree ၏အောက်ခြေမြင်ကွင်းကို print ထုတ်ရန် C ++ ကုဒ်

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

struct node{
    int data;
    node *left, *right;
};

node* create(int data){
    node* tmp = new node();
    tmp->data = data;
    tmp->left = tmp->right = NULL;
    return tmp;
}

int main(){
    node *root = create(2);
    root->left = create(3);
    root->right = create(7);
    root->left->left = create(5);
    root->left->right = create(4);
    root->left->right->left = create(6);

    map<int,int> m;
    queue<pair<int,node*>> q;
    q.push(make_pair(0, root));
    m[0] = root->data;
    while(!q.empty()){
        pair<int, node*> now = q.front();
        q.pop();

        m[now.first] = now.second->data;
        if(now.second->left)
        q.push(make_pair(now.first - 1, now.second->left));
        if(now.second->right)
        q.push(make_pair(now.first + 1, now.second->right));
    }
    for(auto x: m)
        cout<<x.second<<" ";
}
5 6 4 7

Binary Tree အောက်ဆုံးပုံကို print ထုတ်ရန် Java ကုဒ်

import java.util.*;

class node{
  int data;
  node left, right;
  int hd;
}

class Main{

  static node create(int data){
      node tmp = new node();
      tmp.data = data;
      tmp.left = tmp.right = null;
      tmp.hd = 0;
      return tmp;
  }

  public static void main(String[] args){
    node root = create(2);
      root.left = create(3);
      root.right = create(7);
      root.left.left = create(5);
      root.left.right = create(4);
      root.left.right.left = create(6);

      Map<Integer, Integer> m = new TreeMap<Integer, Integer>();
      Queue<node> q = new LinkedList<node>();
      q.add(root);
      m.put(root.hd, root.data);
      while(!q.isEmpty()){
          node now = q.remove();

          m.put(now.hd, now.data);
          if(now.left != null){
          	now.left.hd = now.hd - 1;
          	q.add(now.left);
          }
          if(now.right != null){
          	now.right.hd = now.hd + 1;
          	q.add(now.right);
          }
      }
      for(Map.Entry<Integer, Integer> entry : m.entrySet())
          System.out.print(entry.getValue()+" ");
  }
}
5 6 4 7

ရှုပ်ထွေးဆန်းစစ်ခြင်း

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

အို (NlogN)ဘာလို့လဲဆိုတော့ငါတို့ကသစ်ပင်ကိုဖြတ်ပြီးတန်ဖိုးတွေကိုအဆင့်မြှင့်လိုက်ပြီ။ အဘယ်ကြောင့်ဆိုသော်ကျွန်ုပ်တို့သည်မြေပုံ၊ သွင်းခြင်း၊ ဖျက်ခြင်းနှင့်ရှာဖွေခြင်းကိုအို (logN) အချိန်တွင်ပြုလုပ်သောကြောင့်ဖြစ်သည်။

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

အို (N), အများဆုံးမှာ (N + 1) / 2 ရှိနိုင်ပါသည်နောက်ဆုံးအဆင့်တွင်။ အရှင်အာကာသရှုပ်ထွေး linear ဖြစ်ပါတယ်။