ဒွိသစ်ပင်၏ထောင့်ဖြတ်လမ်းကြောင်း


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် အမေဇုံ အချက်အလက် ဝါသနာရှင်များ လေးကစ် Oracle က PayU Quora
ဒွိသစ်ပင် သစ်ပင် သစ်ပင်လှည့်လည်

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

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

နမူနာ

ဒွိသစ်ပင်၏ထောင့်ဖြတ်လမ်းကြောင်း

2 7
3 4
5 6

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

ပထမ ဦး ဆုံးထောင့်ဖြတ်အဲဒီမှာအတွက် node များ 2, 7 ရှိပါတယ်။ ထို့နောက်ဒုတိယထောင့်ဖြတ်သည် 3, 4 ရှိခြင်းနှင့်တတိယထောင့်ဖြတ် 5, 6 နှင့်အတူတူပင်ဖြစ်သည်။ ထို့ကြောင့် output သည်တူညီသောထောင့်ဖြတ်မျဉ်းမှဒြပ်စင်များသည်တူညီသောမျဉ်းကြောင်း၌ရှိကြောင်းပုံနှိပ်ထုတ်ဝေခဲ့သည်။

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

ဒွိသစ်ပင်၏ထောင့်ဖြတ်လမ်းကြောင်း

ပြproblemနာကညာဘက်အပေါ်ဘက်မှကြည့်ရှုနိုင်သော node များကိုပုံနှိပ်ရန်ကျွန်ုပ်တို့အားတောင်းဆိုသည်။ ဒီတော့ကျွန်တော်တို့ပြproblemနာကိုဘယ်လိုဖြေရှင်းနိုင်မလဲ။

ကျနော်တို့ binary သစ်ပင်တစ်ခု inorder ဖြတ်သန်းပြုလိမ့်မည်။ ဤသို့ပြုလုပ်စဉ်ကျွန်ုပ်တို့သည်အကွာအဝေးကိုထောင့်ဖြတ်လမ်းကြောင်းမှစောင့်ကြည့်မည်။ ဘယ်ဘက်ကိုရွေ့လိုက်တိုင်းထောင့်ဖြတ်အကွာအဝေးသို့ ၁ ထည့်သည်။ လမ်းကြောင်းမှန်သို့ရွေ့လျှင်မည်သည့်တန်ဖိုးမျှထပ်ပေါင်းထည့်မည်မဟုတ်ပါ။ ထို့ကြောင့်၊ ၎င်းကိုလုပ်နေစဉ်ကျွန်ုပ်တို့သည် ၀ င်ရောက်နေသော node များကိုခြေရာခံနိုင်လိမ့်မည် မြေပုံ။ ထောင့်ဖြတ်အကွာအဝေးနှင့်မြေပုံကိုတန်ဖိုးအဖြစ်ပြထားသောမြေပုံကိုကျွန်ုပ်တို့ဖန်တီးမည်။ ဘာဖြစ်လို့လဲဆိုတော့ကျွန်တော်တို့ဟာ vector တစ်ခုမှာထောင့်ဖြတ်အကွာအဝေးနှင့် node များထည့်ပါလိမ့်မယ်။ ငါတို့သည်တပြင်လုံးကိုဖြတ်သန်းကြလိမ့်မယ်အဖြစ် သစ်ပင်။ အဆိုပါဖြတ်သန်းပြီးနောက်ကျနော်တို့ကသူတို့ထောင့်ဖြတ်အကွာအဝေးနှုန်းအတိုင်း virus သယ်ဆောင်အတွက် node များထားရှိမည်လိမ့်မယ်။

ဤတွက်ချက်မှုများအားလုံးပြီးသွားလျှင်၊ nctors မှတစ်ခုချင်းစီမှ node များကိုခွဲထုတ်ရင်းမြေပုံရှိ element များကိုသာပုံနှိပ်ပါ။

Binary Tree of Diagonal Traversal ကို print ထုတ်ရန် C ++ code

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

void diagonalView(node* root, int dis, map<int, vector<int>> &m){
    if(root){
        m[dis].push_back(root->data);
        // move in the left direction with dis+1 distance
        diagonalView(root->left, dis+1, m);
        // move in the right direction with dis distance
        diagonalView(root->right, dis, m);
    }
}

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, vector<int>> m;
    diagonalView(root, 0, m);
    for(auto x: m){
        for(auto nodes: x.second)
            cout<<nodes<<" ";
        cout<<endl;
    }
}
2 7
3 4
5 6

Binary Tree of Diagonal Traversal ကို print ထုတ်ရန် Java code

import java.util.*;

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

class Main{

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

  static void diagonalView(node root, int dis, Map<Integer, Vector<Integer>> m){
      if(root != null){
      	Vector<Integer> v = m.get(dis);
      	if(v == null){
      		v = new Vector<Integer>();
      		v.add(root.data);
      	}
      	else
      		v.add(root.data);
          m.put(dis, v);
          // move in the left direction with dis+1 distance
          diagonalView(root.left, dis+1, m);
          // move in the right direction with dis distance
          diagonalView(root.right, dis, m);
      }
  }

  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, Vector<Integer>> m = new TreeMap<Integer, Vector<Integer>>();
      diagonalView(root, 0, m);
      for(Map.Entry<Integer, Vector<Integer>> entry : m.entrySet())
          System.out.println(entry.getValue());
  }
}
[2, 7]
[3, 4]
[5, 6]

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

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

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

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

အို (N)၊ ဘာလို့လဲဆိုတော့ငါတို့မြေပုံမှာရှိတဲ့ node တွေအားလုံးကိုသိုလှောင်ထားလို့ပဲ။ အဆိုပါအာကာသရှုပ်ထွေး linear ဖြစ်ပါတယ်။