İkili bir ağacın sağ görünüşünü çap edin

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Akkolit Çiy kərpic Amazon MakeMyTrip Snapdeal
İkili ağac Ağac Ağacın keçidiBaxılıb 24

Problem bəyanat

"İkili bir ağacın sağ görünüşünü çap et" problemi sizə ikili bir ağac verildiyini bildirir. İndi bu ağacın düzgün görünüşünü tapmaq lazımdır. Burada ikili ağacın düzgün görünüşü, düzgün istiqamətdən baxıldığında ağacın göründüyü kimi ardıcıllığı çap etmək deməkdir.

misal

İkili bir ağacın sağ görünüşünü çap edinPin

2 7 4 6

Izahat

İkili ağacı düzgün istiqamətdə müşahidə edirsinizsə. Çıxışda yalnız basılmış qovşaqları görə bilirik. Çünki 3 və 5 qovşaqları sırasıyla 7 və 4 arxasında gizlənir.

İkili ağacın sağ görünüşünü çap etmək üçün yanaşma

Bu problemdə doğru baxışı tapmalıyıq ikili ağac. Problem iki yanaşma ilə həll edilə bilər. Onlardan biri növbə, digəri isə rekursiyadan istifadə edir. Əvvəlcə növbədən istifadə edərək yanaşmanı müzakirə edəcəyik. Yəni a. İstifadə edərək problemi həll etmək queue. İkili ağacın kökündən başlayırıq. Ağacın hər səviyyəsi üçün qovşaqları növbədə saxlamağa davam edirik. Növbəti səviyyə düyünlərini saxlamaq üçün cari səviyyə düyünlərini keçməliyik. Beləliklə, mövcud səviyyənin qovşaqlarının üstündən keçərkən. Son nodu bu səviyyədə çap edirik. Ağacı sağ tərəfdən müşahidə etdiyimiz zaman. Bizə görünən yeganə düyün bir səviyyədə ən sağ düyündür. Bu yanaşma yer tutan bir növbədən istifadə edir.

Rekursiyadan istifadə edərək həll yolunu müzakirə edək. Çözüm ağacın sol görünüşünü tapmaqla çox oxşardır. Bu yanaşmada. Sadəcə, ağacın kənar keçidlə zidd olan bir hərəkətini edirik. Bununla yanaşı, hazırda olduğumuz səviyyəni və indiyə qədər əldə etdiyimiz maksimum səviyyəni də izləyirik. Sol alt ağacdan əvvəl sağ alt ağaca keçərkən. Hər dəfə ağacda yeni səviyyəyə qədəm qoyuruq. Əvvəlcə ən sağ düyünlə qarşılaşırıq. Beləliklə, cari səviyyənin maksimum səviyyədən çox olub olmadığını həmişə yoxlayırıq, düyünü çap edirik. Tərtibçi yığını üçün lazım olan yeri nəzərə almırıqsa, yanaşma daha yaxşıdır. Problemin yerdəki mürəkkəbliyi, kompilyator yığınının götürdüyü boşluğu nəzərə alsaq, ağacın hündürlüyündən asılıdır.

Kodu

İkili bir ağacın sağ görünüşünü çap etmək üçün C ++ kodu

#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

İkili Ağacın Sağ Görünüşünü Yazdırmaq üçün Java kodu

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N), sadəcə ağacdakı qovşaqların üstündən keçirik. Yəni ağacda N qovşaq varsa, alqoritm O (N) əməliyyatlarının yerinə yetirilməsini tələb edir.

Kosmik Mürəkkəblik

O (1). Tərtibçi yığınının istifadə etdiyi yer nəzərə alınmırsa, başqa bir şey O (H) yer tələb olunur.

Translate »