Хоёртын модны баруун үзэмжийг хэвлэх  


Хэцүү байдлын түвшин Easy
Байнга асуудаг Accolite Adobe Амазоны MakeMyTrip Snapdeal
Хоёртын мод Мод Мод хөндлөн гарах

Асуудлын мэдэгдэл  

“Хоёртын модны зөв харагдацыг хэвлэх” гэсэн асуудалд танд хоёртын мод өгдөг гэж заасан байдаг. Одоо та энэ модны зөв үзэмжийг олох хэрэгтэй. Энд хоёртын модны зөв харагдана гэдэг нь зөв чиглэлээс харахад мод харагдаж байгаа тул дарааллыг хэвлэнэ гэсэн үг юм.

Жишээ нь  

Хоёртын модны баруун үзэмжийг хэвлэхPin

2 7 4 6

Тайлбар

Хэрэв та хоёртын модыг зөв чиглэлд ажиглавал. Бид зөвхөн гаралтанд хэвлэгдсэн зангилаа харах боломжтой. Учир нь 3 ба 5 зангилаа тус тус 7 ба 4-ийн ард нуугддаг.

Хоёртын модны зөв дүр төрхийг хэвлэх арга  

Энэ асуудалд бид зөв ойлголтыг олох хэрэгтэй хоёртын мод. Асуудлыг хоёр хандлагыг ашиглан шийдвэрлэх боломжтой. Тэдгээрийн нэг нь дараалал, нөгөө нь рекурс ашигладаг. Нэгдүгээрт, бид дарааллыг ашиглах хандлагын талаар ярилцах болно. Тиймээс асуудлыг ашиглан a дараалал. Бид хоёртын модны үндэснээс эхэлдэг. Модны түвшин тус бүрт бид зангилаагаа дараалалд хадгалсаар байдаг. Дараагийн түвшний зангилааг хадгалахын тулд бид одоогийн түвшний зангилаануудыг дайран өнгөрөх ёстой. Тиймээс бид одоогийн түвшний зангилаагаар дайрч өнгөрөхдөө. Бид энэ түвшинд хамгийн сүүлийн зангилаа хэвлэнэ. Модыг баруун талаас нь ажиглахад. Бидэнд харагдах цорын ганц зангилаа бол түвшний хамгийн баруун цэг юм. Энэ арга нь зай эзэлдэг дарааллыг ашигладаг.

мөн үзнэ үү
Илүү их давтамжтай элемент байхаар хоёр элементийн давтамжийн хоорондох хамгийн их ялгаа

Рекурси ашиглан шийдлийн талаар ярилцъя. Энэ шийдэл нь модны зүүн үзэмжийг олохтой маш төстэй юм. Энэ хандлагад. Бид зүгээр л модны хөндлөн огтлолын эсрэг талыг хөндлөн гаргадаг. Гэхдээ бид одоо байгаа түвшин, өнөөг хүртэл хүрсэн хамгийн дээд түвшинг хянах болно. Зүүн модны өмнө баруун дэд мод руу шилжихэд. Бид модны шинэ түвшинд орох бүрт. Бид эхлээд хамгийн зөв зангилаатай тулгардаг. Тиймээс бид одоогийн түвшин хамгийн дээд түвшингээс их байгаа эсэхийг үргэлж шалгаж, зангилааг хэвлэдэг. Хэрэв бид хөрвүүлэгч стекд шаардлагатай зайг тооцохгүй бол арга нь илүү дээр юм. Асуудлын орон зайн нарийн төвөгтэй байдал нь хөрвүүлэгч стекийн авсан зайг авч үзвэл модны өндрөөс хамаарна.

код  

Хоёртын модны баруун үзэмжийг хэвлэх 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;
}

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

Хоёртын модны баруун үзэмжийг хэвлэх Java код

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

Нарийн төвөгтэй байдлын шинжилгээ  

Цаг хугацааны нарийн төвөгтэй байдал

O (N), бид зүгээр л модны зангилаа дээгүүр явж байна. Тиймээс модонд N зангилаа байгаа бол алгоритм нь O (N) үйлдлийг гүйцэтгэхийг шаарддаг.

мөн үзнэ үү
Хоёр мод ижил байгаа эсэхийг тодорхойлохын тулд код бич

Сансрын нарийн төвөгтэй байдал

O (1). Хэрэв хөрвүүлэгч стекийн ашигласан зайг тооцохгүй бол өөрөөр O (H) зай шаардагдана.