प्रीऑर्डर ट्रैवर्सल से बीएसटी का पोस्टऑर्डर ट्रावेलर खोजें


कठिनाई स्तर मध्यम
में अक्सर पूछा वीरांगना चौपाई PayU
बाइनरी सर्च ट्री वृक्ष का त्राटक

समस्या का विवरण

समस्या "प्रीऑर्डर ट्रैवर्सल से बीएसटी के पोस्टऑर्डर ट्रावेलर्स खोजें" में कहा गया है कि आपको बाइनरी सर्च ट्री का प्रीव्यूअर ट्रैवर्सल दिया जाता है। फिर दिए गए इनपुट का उपयोग करके पोस्टऑर्डर ट्रैवर्सल खोजें।

उदाहरण

प्रीऑर्डर ट्रैवर्सल से बीएसटी का पोस्टऑर्डर ट्रावेलर खोजें

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

दृष्टिकोण

दी गई समस्या कहती है कि हमें बाइनरी सर्च ट्री के प्रीऑर्डर ट्रैवर्सल अनुक्रम के साथ प्रदान किया गया है। अब हमें पेड़ के पोस्टऑर्डर ट्रावेलर को खोजने की आवश्यकता है, जिसमें इनपुट के समान एक ही ट्रॉलर ट्रॉलर है। हमें इस समस्या को कुशलता से हल करने की आवश्यकता है।

सबसे पहले एक भोली दृष्टिकोण का उपयोग करना है अग्रिम आदेश ट्रैवर्सल और निर्माण BST। फिर बस इस नवनिर्मित पेड़ के ऊपर एक पोस्टऑर्डर ट्रैवर्सल करें। लेकिन यह दृष्टिकोण अंतरिक्ष के बारे में अक्षम है। क्योंकि निर्मित पेड़ एक उपरि के रूप में कार्य कर रहा है।

समस्या को कुशलता से हल करने के लिए, हम इनपुट ऐरे से गुजरते हैं। इनपुट ऐरे हमारे प्रीवार्ड ट्रैवर्सल हैं। इसलिए हम प्रीऑर्डर ट्रैवर्सल से गुजरते हैं और पाते हैं कि क्या मौजूदा तत्व को झूठ बोलना चाहिए। जब हम पहले तत्व से शुरू करते हैं तो हम न्यूनतम पूर्णांक मान से अधिकतम पूर्णांक मान तक की सीमा निर्धारित करते हैं। क्योंकि प्रीऑर्डर ट्रैवर्सल में बाएं और दाएं सबट्री से पहले रूट है। हम जानते हैं कि यदि बायाँ उपमान मौजूद है तो तत्वों को न्यूनतम पूर्णांक मान से मूल से कम मान लेना चाहिए। इसी तरह से सही सबट्री के लिए जो अधिक से अधिक रूट के मूल्य से अधिकतम पूर्णांक मान तक झूठ होना चाहिए। अब यदि वर्तमान तत्व इस सीमा में नहीं है। फिर उस दूसरे सबट्री में झूठ बोलना चाहिए (यदि ऐसा है तो लेफ्ट सबट्री के लिए रेंज में झूठ नहीं बोलना चाहिए, क्योंकि उसे सही सबट्री और इसके विपरीत में झूठ बोलना चाहिए)।

कोड

C ++ कोड, प्रीऑर्डर ट्रैवर्सल से 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

जटिलता विश्लेषण

समय जटिलता

पर), क्योंकि हमें दिए गए सरणी के पूरे भाग को पार करना है।

अंतरिक्ष जटिलता

पर), क्योंकि संकलक कार्यों के लिए इस्तेमाल किया जा रहा है जो कंपाइलर स्टैक के कारण।