တစ် ဦး Binary Tree ၏ညာဘက်ပုံနှိပ်ပါ


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် Accolite Adobe က အမေဇုံ ကွမ်းခြံကုန်း Snapdeal
ဒွိသစ်ပင် သစ်ပင် သစ်ပင်လှည့်လည်

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

ပြinaryနာက“ Binary Tree of Right View” ကိုပုံနှိပ်ပါ။ ယခုသင်သည်ဤသစ်ပင်၏မှန်ကန်သောမြင်ကွင်းကိုရှာဖွေရန်လိုအပ်သည်။ ဤနေရာတွင် binary tree ၏ညာဘက်မြင်ကွင်းသည်လမ်းကြောင်းမှန်မှကြည့်လိုက်သောအခါသစ်ပင်ကြည့်လိုက်သည့်အတိုင်း sequence ကို print ထုတ်ရန်ဖြစ်သည်။

နမူနာ

တစ် ဦး Binary Tree ၏ညာဘက်ပုံနှိပ်ပါ

2 7 4 6

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

သငျသညျလမ်းကြောင်းမှန်ပေါ်အတွက်ဒွိသစ်ပင်စောင့်ရှောက်လျှင်။ ကျနော်တို့ output ကိုအတွက်ပုံနှိပ်သော node များသာကြည့်ရှုနိုင်ကြသည်။ ဘာဖြစ်လို့လဲဆိုတော့ node များ 3 နှင့် 5 သည် 7 နဲ့ 4 အသီးသီးနောက်ကွယ်မှာဝှက်ထားလို့ပဲ

binary သစ်ပင်၏ညာဘက်မြင်ကွင်းပုံနှိပ်ရန်ချဉ်းကပ်ပါ

ဤပြproblemနာတွင်ကျွန်ုပ်တို့သည်မှန်ကန်သောအမြင်ကိုရှာဖွေရန်လိုအပ်သည် ဒွိသစ်ပင်။ အဆိုပါပြproblemနာကိုနည်းလမ်းနှစ်ခုသုံးပြီးဖြေရှင်းနိုင်ပါတယ်။ သူတို့ထဲကတစ်ခုကလူတန်းကိုသုံးတယ်၊ နောက်တစ်ခုကတော့ပြန်လုပ်တယ်။ ပထမ ဦး စွာကျွန်ုပ်တို့သည်တန်းစီ အသုံးပြု၍ ချဉ်းကပ်မှုကိုဆွေးနွေးပါမည်။ ဒီတော့ပြusingနာကိုဖြေရှင်းခြင်းဖြင့် ဆံပင်ကြိုး။ ကျနော်တို့ binary သစ်ပင်၏အမြစ်မှစ။ သစ်ပင်၏အဆင့်တစ်ခုစီအတွက်ကျွန်ုပ်တို့သည်အဆက်မပြတ်အတွင်းရှိ node များကိုသိုလှောင်ထားသည်။ နောက်တစ်ဆင့်၏ node များကိုသိုလှောင်ရန်အတွက်ကျွန်ုပ်တို့သည်လက်ရှိအဆင့်ရှိ node များကိုဖြတ်ကျော်ရမည်။ ဒါကြောင့်ကျနော်တို့ကလက်ရှိအဆင့် node များကျော်ဖြတ်သန်းကြသောအခါ။ ဒီအဆင့်မှာနောက်ဆုံး node ကို print ထုတ်တယ်။ ကျနော်တို့လက်ျာဘက်အနေဖြင့်သစ်ပင်စောင့်ရှောက်တဲ့အခါ။ ကျွန်တော်တို့ကိုမြင်နိုင်တဲ့တစ်ခုတည်းသော node တစ်ခုကတော့ level မှာ rightmost node ဖြစ်တယ်။ ဒီချဉ်းကပ်မှုကနေရာယူတဲ့တန်းစီကိုအသုံးပြုသည်။

ဖြေရှင်းနည်းကိုသုံးပြီးဖြေရှင်းနည်းကိုဆွေးနွေးကြရအောင်။ အဖြေသည်သစ်ပင်၏ဘယ်ဘက်မြင်ကွင်းကိုရှာဖွေခြင်းနှင့်အလွန်ဆင်တူသည်။ ဒီချဉ်းကပ်မှု၌။ ကျွန်ုပ်တို့သည်သစ်ပင်တစ်ပင်ကိုဖြတ်သွားခြင်းကိုအတွင်းကူးဖြတ်ခြင်းနှင့်ဆန့်ကျင်ဘက်ဖြစ်သည်။ ဒါပေမယ့်လည်းကျွန်ုပ်တို့လက်ရှိရောက်ရှိနေသည့်အဆင့်နှင့်ယခုအထိအများဆုံးရရှိသောအဆင့်ကိုလည်းခြေရာခံနိုင်သည်။ ဘယ်ဘက် subtree မတိုင်ခင်ညာဘက် subtree ကိုရွှေ့တဲ့အခါ။ သစ်ပင်ပေါ်ကအဆင့်တိုင်းကိုရောက်တိုင်း။ ကျနော်တို့ပထမဆုံးညာဘက် node ကိုကြုံတွေ့ရ။ ထို့ကြောင့်ကျွန်ုပ်တို့သည်လက်ရှိအဆင့်သည်အများဆုံးအဆင့်ထက်ပိုမိုကြီးမြတ်မလားစစ်ဆေးသည်၊ node ကိုကျွန်ုပ်တို့ print ထုတ်သည်။ ကျွန်ုပ်တို့သည် compiler stack အတွက်လိုအပ်သောနေရာကိုမစဉ်းစားပါကချဉ်းကပ်မှုပိုကောင်းသည်။ အကယ်၍ ကျွန်ုပ်တို့သည် compiler stack မှသိမ်းဆည်းထားသောနေရာကိုစဉ်းစားပါကပြproblemနာအတွက် space ရှုပ်ထွေးခြင်းသည်သစ်ပင်၏အမြင့်ပေါ်တွင်မူတည်သည်။

ကုဒ်

Binary Tree ၏ညာဘက်မြင်ကွင်းပုံနှိပ်ရန် 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 printRightView(node* root, int level, int &max_level){
    if(root){
        if(level > max_level){
            max_level = level;
            cout << root->data <<" ";
        }
        printRightView(root->right, level+1, max_level);
        printRightView(root->left, level+1, max_level);
    }
}

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);

  int max_level = 0;
  printRightView(root, 1, max_level);
}
2 7 4 6

Binary Tree ၏ညာဘက်မြင်ကွင်းပုံနှိပ်ရန် Java code

import java.util.*;

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

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

  static int max_level;
  static void printRightView(node root, int level){
      if(root != null){
          if(level > max_level){
              max_level = level;
              System.out.print(root.data+" ");
          }
          printRightView(root.right, level+1);
          printRightView(root.left, level+1);
      }
  }

  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);
    
    max_level = 0;
    printRightView(root, 1);
  }
}
2 7 4 6

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

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

အို (N)၊ ကျနော်တို့သစ်ပင်ရှိ node များကျော်ဖြတ်သန်းနေကြသည်။ သစ်ပင်ထဲတွင် N node များရှိပါက algorithm သည် O (N) လုပ်ဆောင်ရန်လိုအပ်သည်။

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

အို (၁) compiler stack အသုံးပြုသောအာကာသကိုမစဉ်းစားပါက၊ အို (H) နေရာလိုအပ်သည်။