बाइनरी रूखको दायाँ दृश्य प्रिन्ट गर्नुहोस्


कठिनाई तह सजिलो
बारम्बार सोधिन्छ समग्र एडोब अमेजन MakeMyTrip स्नैपडल
बाइनरी रूख ट्री रूख ट्राभर्सल

समस्या वक्तव्य

समस्या "बाइनरी रूखको दायाँ दृश्य प्रिन्ट गर्नुहोस्" भन्छन् कि तपाईंलाई बाइनरी रूख दिइन्छ। अब तपाईंले यस रूखको सहि दृश्य फेला पार्न आवश्यक छ। यहाँ, बाइनरी रूखको दायाँ दृश्यको अर्थ अनुक्रम मुद्रण गर्नु भनेको रूख सही दिशाबाट हेरे पछि देखिन्छ।

उदाहरणका

बाइनरी रूखको दायाँ दृश्य प्रिन्ट गर्नुहोस्

2 7 4 6

स्पष्टीकरण

यदि तपाइँ बाइनरी रूखलाई सही दिशामा हेर्नुहुन्छ। हामी केवल नोडहरू देख्न सक्षम हुन्छौं जुन आउटपुटमा प्रिन्ट भएको छ। किनकि नोड्स and र respectively क्रमश: and र behind पछाडि लुक्छन्।

बाइनरी रूखको दायाँ दृश्य प्रिन्ट गर्न दृष्टिकोण

यस समस्यामा हामीले यसको सही दृष्टिकोण खोज्नुपर्दछ बाइनरी रूख। समस्या दुई दृष्टिकोण प्रयोग गरेर समाधान गर्न सकिन्छ। ती मध्ये एकले एक लाम प्रयोग गर्दछ र अर्कोले रिकर्सन प्रयोग गर्दछ। पहिले हामी क्यु लाई प्रयोग गरेर दृष्टिकोणको बारेमा छलफल गर्नेछौं। त्यसो भए समस्या समाधान गर्न a को प्रयोग गरी लाम। हामी बाइनरी रूखको जराबाट शुरू गर्दछौं। रूखको प्रत्येक स्तरको लागि, हामी लाममा नोडहरू भण्डार गर्न जारी राख्छौं। अर्को स्तरको नोडहरू भण्डारण गर्न, हामीले हालको तहको नोडहरू पार गर्नुपर्दछ। त्यसोभए जब हामी हालको तहको नोडहरू पार गर्दैछौं। हामी यस स्तरमा अन्तिम नोड प्रिन्ट गर्दछौं। जब हामी रूखलाई दायाँ पट्टिबाट अवलोकन गर्दछौं। केवल नोड जुन हामीलाई देखिने छ केवल स्तरमा दायाँ नोड हो। यस दृष्टिकोणले ठाउँ लिने प que्क्ति प्रयोग गर्दछ।

पुनरावृत्ति प्रयोग गरेर समाधान छलफल गरौं। समाधान रूखको बाँया दृश्य खोज्नु जस्तै मिल्दोजुल्दो छ। यस दृष्टिकोणमा हामी केवल रूखको एउटा ट्रान्सभर्ल गर्छौं जुन ईन्डर ट्रभर्सलको विपरित हुन्छ। तर हामी त्यस स्तरलाई पनि ट्र्याक गर्छौं जुन हामी अहिले छौं र अधिकतम स्तर अहिले सम्म प्राप्त गर्यौं। हामी बायाँ subtree अघि दायाँ subtree मा सार्न को रूप मा। जब हामी रूखमा नयाँ स्तर प्रवेश गर्छौं। हामीले पहिले दायाँ नोड भेट्यौं। त्यसैले हामी जहिले पनि एक जाँच राख्छौं यदि हालको स्तर अधिकतम स्तर भन्दा ठूलो छ भने, हामी नोड प्रिन्ट गर्दछौं। यदि हामी कम्पाइलर स्ट्याकको लागि आवश्यक स्थान विचार गर्दैनौं भने यो दृष्टिकोण राम्रो छ। समस्याको लागी अन्तरिक्ष जटिलता रूखको उचाईमा निर्भर हुन्छ यदि हामी कम्पाइलर स्ट्याकले लिने ठाउँलाई ध्यान दियौं भने।

कोड

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 (१) यदि कम्पाइलर स्ट्याकले प्रयोग गरेको खाली ठाउँमा मानिदैन भने, अन्यथा ओह) ठाउँ आवश्यक छ।