प्रीऑर्डर ट्रॅव्हर्सल वरून बीएसटीचे पोस्टऑर्डर ट्रव्हर्सल शोधा  


अडचण पातळी मध्यम
वारंवार विचारले ऍमेझॉन फोरकाइट्स पीएयू
बायनरी शोध वृक्ष ट्री ट्रॅव्हर्सल

समस्या विधान  

“प्रीऑर्डर ट्रॅव्हर्सलपासून बीएसटीचे पोस्टऑर्डर ट्रॅव्हर्सल शोधा” ही समस्या सांगते की आपल्याला बायनरी शोध वृक्षाचे प्रीऑर्डर ट्रॅव्हर्सल दिले गेले आहे. नंतर दिलेला इनपुट वापरुन पोस्टऑर्डर ट्रॅव्हर्सल शोधा.

उदाहरण  

प्रीऑर्डर ट्रॅव्हर्सल वरून बीएसटीचे पोस्टऑर्डर ट्रव्हर्सल शोधापिन  

preorder traversal sequence: 5 2 1 3 4 7 6 8 9
1 4 3 2 6 9 8 7 5

दृष्टीकोन  

दिलेली समस्या सांगते की आम्हाला बायनरी शोध वृक्षाची प्रीऑर्डर ट्रॅव्हर्सल अनुक्रम प्रदान केले गेले आहे. आता आम्हाला इनपुट प्रमाणेच प्रीऑर्डर ट्रॅव्हर्सल असलेल्या झाडाचे पोस्टऑर्डर ट्रॅव्हर्सल शोधणे आवश्यक आहे. आम्हाला ही समस्या कार्यक्षमतेने सोडविणे आवश्यक आहे.

एक निष्क्रीय दृष्टीकोन प्रथम वापरणे आहे ऑर्डरपूर्वीसाठी आक्रमक आणि तयार BST. मग नव्याने तयार झालेल्या या झाडावर पोस्टऑर्डर ट्रॅव्हर्सल करा. परंतु जागेबाबत हा दृष्टिकोन अकार्यक्षम आहे. कारण बांधलेले झाड ओव्हरहेड म्हणून काम करत आहे.

समस्येचे कार्यकुशलतेचे निराकरण करण्यासाठी आम्ही इनपुट अ‍ॅरेमधून जात आहोत. इनपुट अ‍ॅरे आमची प्रीऑर्डर ट्रॅव्हर्सल आहे. म्हणून आम्ही प्रीऑर्डर ट्रॅव्हर्सलमधून जातो आणि सद्य घटक खोटे बोलू शकतो की नाही हे शोधू. जेव्हा आम्ही पहिल्या घटकासह प्रारंभ करतो तेव्हा आम्ही किमान पूर्णांक मूल्यापासून कमाल पूर्णांक मूल्यापर्यंत श्रेणी सेट करतो. कारण प्रीऑर्डर ट्रॅव्हर्सलमध्ये डावी आणि उजवीक सबट्री आधी मूळ असते. आम्हाला माहित आहे की जर डावे सबट्री अस्तित्त्वात असेल तर घटक कमीतकमी पूर्णांक मूल्यापासून मूळपासून कमी मूल्यापर्यंत खाली असावेत. त्याचप्रमाणे उजव्या सबट्रीसाठी जे मोठ्या रूटच्या मूल्यापासून ते जास्तीत जास्त पूर्णांक मूल्यापर्यंत असले पाहिजे. आता जर विद्यमान घटक या श्रेणीमध्ये नसेल तर. मग ते दुसर्‍या सबट्रीमध्ये पडून असावे (म्हणजेच ते डावीकडील सबट्रीच्या रेंजमध्ये नसले तरी उजव्या सबट्री आणि त्याउलट उलट असेल).

हे सुद्धा पहा
बायनरी ट्रीमध्ये जास्तीत जास्त पातळीची बेरीज शोधा

कोड  

प्रीऑर्डर ट्रॅव्हर्सलपासून बीएसटीचे पोस्टऑर्डर ट्रव्हर्सल शोधण्यासाठी सी ++ कोड

#include<bits/stdc++.h>
using namespace std;

void preToPost(int input[], int n, int mn, int mx, int& idx)
{
  // base case
  if (idx == n)
    return;
  // if current element does not belong to current subtree
  if (input[idx] < mn || input[idx] > mx) {
    return;
  }

  // store the value of root ro print after printing its subtrees
  int root = input[idx];
  idx++;

  // recursively solve for left and right subtree
  preToPost(input, n, mn, root, idx);
  preToPost(input, n, root, mx, idx);
  // print root
  cout<<root<<" ";
}

int main()
{
  int input[] = {5, 2, 1, 3, 4, 7, 6, 8, 9};
  int n = (sizeof input)/(sizeof input[0]);
  int idx = 0;
  	preToPost(input, n, INT_MIN, INT_MAX, idx);
}
1 4 3 2 6 9 8 7 5

प्रीऑर्डर ट्रॅव्हर्सलपासून बीएसटीचे पोस्टऑर्डर ट्रव्हर्सल शोधण्यासाठी जावा कोड

import java.util.*;

class Main{
  static int idx = 0;
  static void preToPost(int input[], int n, int mn, int mx)
  {
    // base case
    if (idx == n)
      return;
    // if current element does not belong to current subtree
    if (input[idx] < mn || input[idx] > mx) {
      return;
    }

    // store the value of root ro print after printing its subtrees
    int root = input[idx];
    idx++;

    // recursively solve for left and right subtree
    preToPost(input, n, mn, root);
    preToPost(input, n, root, mx);
    // print root
    System.out.print(root+" ");
  }

  public static void main(String[] args)
  {
    int input[] = {5, 2, 1, 3, 4, 7, 6, 8, 9};
    int n = input.length;
    	preToPost(input, n, Integer.MIN_VALUE, Integer.MAX_VALUE);
  }
}
1 4 3 2 6 9 8 7 5

गुंतागुंत विश्लेषण  

वेळ कॉम्प्लेक्सिटी

ओ (एन), कारण आपल्याला दिलेल्या अ‍ॅरेचा संपूर्ण भाग ओलांडावा लागेल.

स्पेस कॉम्प्लेक्सिटी

ओ (एन)कंपाइलर स्टॅकमुळे जे रिकर्सिव्ह फंक्शन्ससाठी वापरले जात आहे.