დაბეჭდეთ ორობითი ხის მარჯვენა ხედი


Რთული ტური Easy
ხშირად ეკითხებიან თანამოსაყრელი Adobe Amazon MakeMyTrip Snapdeal
ორობითი ხე ხე ხის გადაკვეთა

პრობლემის განცხადება

პრობლემა "ორობითი ხის სწორი გამოსახულების დაბეჭდვა" აცხადებს, რომ თქვენ გეძლევათ ორობითი ხე. ახლა თქვენ უნდა იპოვოთ ამ ხის სწორი ხედი. აქ, ორობითი ხის სწორი ხედი ნიშნავს მიმდევრობის დაბეჭდვას, რადგან ხე გამოიყურება, როდესაც სწორი მიმართულებით გამოიყურება.

მაგალითი

დაბეჭდეთ ორობითი ხის მარჯვენა ხედი

2 7 4 6

განმარტება

თუ ორობით ხეს სწორი მიმართულებით დააკვირდებით. ჩვენ შეგვიძლია დავინახოთ მხოლოდ კვანძები, რომლებიც დაბეჭდილია გამომავალში. რადგან 3 და 5 კვანძები იმალება შესაბამისად 7 და 4 კვანძებს.

ორობითი ხის სწორი ხედვის ამობეჭდვის მიდგომა

ამ პრობლემის დროს, ჩვენ უნდა ვიპოვოთ სწორი ხედი ორობითი ხე. პრობლემის გადაჭრა შესაძლებელია ორი მიდგომის გამოყენებით. ერთი რიგს იყენებს, ხოლო მეორე - რეკურსიას. პირველ რიგში, განვიხილავთ რიგის გამოყენებას. ასე რომ, პრობლემის გადასაჭრელად ა მდგომ. ჩვენ ვიწყებთ ორობითი ხის ფესვიდან. ხის თითოეული დონისთვის, ჩვენ ვაგრძელებთ კვანძების შენახვას რიგში. შემდეგი დონის კვანძების შესანახად, ჩვენ უნდა გადავკვეთოთ მიმდინარე დონის კვანძებს. ასე რომ, როდესაც ჩვენ გადავდივართ მიმდინარე დონის კვანძებზე. ჩვენ ამ დონეზე ვბეჭდავთ ბოლო კვანძს. როდესაც ხეზე ვაკვირდებით ხეს. ერთადერთი კვანძი, რომელიც ჩვენთვის ჩანს, არის ყველაზე სწორი კვანძი დონეზე. ეს მიდგომა იყენებს რიგს, რომელიც ადგილს იკავებს.

განვიხილოთ გამოსავალი რეკურსის გამოყენებით. გამოსავალი ძალიან ჰგავს ხის მარცხენა ხედვის პოვნას. ამ მიდგომაში. ჩვენ უბრალოდ ვაკეთებთ ხის გადაკვეთას, რომელიც საწინააღმდეგოა უგულებელყოფის უგულებელყოფისაგან. ჩვენ ასევე ვადევნებთ თვალყურს იმ დონეს, რომელზეც ამჟამად ვართ და მაქსიმალურ დონეზე მიღწეულია. როგორც ჩვენ გადავდივართ მარჯვენა ქვედა ხისკენ მარცხენა ქვეტყემდე. ყოველთვის, როდესაც ხეში ახალ დონეზე შევალთ. ჩვენ პირველად გვხვდება ყველაზე სწორი კვანძი. ასე რომ, ჩვენ ყოველთვის ვატარებთ შემოწმებას, არის თუ არა ამჟამინდელი დონე მაქსიმალურზე მეტი, ჩვენ ბეჭდავს კვანძს. მიდგომა უკეთესია, თუ არ გავითვალისწინებთ შემდგენლის დასტისთვის საჭირო ადგილს. პრობლემის სივრცის სირთულე დამოკიდებულია ხის სიმაღლეზე, თუ გავითვალისწინებთ შემდგენლის სტეკის მიერ გატარებულ ადგილს.

კოდი

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

ჯავა კოდი ორობითი ხის მარჯვენა სანახავად დასაბეჭდად

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) საჭიროა სივრცე.