सी ++ में प्रीऑर्डर ट्रैवर्सल से एक पेड़ पुनर्प्राप्त करें

मान लीजिए कि एक बाइनरी ट्री है। हम एक बाइनरी ट्री की जड़ पर एक प्रीऑर्डर डेप्थ फर्स्ट सर्च चलाएंगे।

इस ट्रैवर्सल में प्रत्येक नोड पर, आउटपुट डैश की डी संख्या होगी (यहां डी इस नोड की गहराई है), उसके बाद हम इस नोड का मान प्रदर्शित करते हैं। जैसा कि हम जानते हैं कि यदि किसी नोड की गहराई D है, तो उसके तत्काल बच्चे की गहराई D+1 है और रूट नोड की गहराई 0 है।

एक और बात हमें ध्यान में रखनी होगी कि यदि किसी नोड में केवल एक बच्चा है, तो उस बच्चे के बाएं बच्चे होने की गारंटी है। इसलिए, यदि इस ट्रैवर्सल का आउटपुट S दिया गया है, तो पेड़ को पुनः प्राप्त करें और उसकी जड़ को वापस करें।

इसलिए, यदि इनपुट "1-2--3--4-5--6--7" जैसा है, तो आउटपुट होगा

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक स्टैक सेंट परिभाषित करें

• मैं:=0, एन:=एस का आकार

• एलवीएल:=0, अंक:=0

• जबकि मैं

  • इनिशियलाइज़ lvl के लिए:=0, जब S[i] '-' के समान हो, तो अपडेट करें (lvl को 1 से बढ़ाएँ), (i को 1 से बढ़ाएँ), करें -

    • कुछ न करें

  • संख्या :=0

  • जबकि (i

    • संख्या:=संख्या * 10 + (एस [i] - '0')

    • (i 1 से बढ़ाएँ)

  • जबकि st> lvl का आकार, करें −

    • सेंट से तत्व हटाएं

  • अस्थायी =संख्या मान के साथ एक नया ट्री नोड बनाएं

  • यदि st खाली नहीं है और st का शीर्ष तत्व खाली नहीं है, तो -

    • सेंट के शीर्ष तत्व के बाईं ओर:=अस्थायी

  • अन्यथा जब st खाली न हो, तब -

    • सेंट के शीर्ष तत्व का अधिकार:=अस्थायी

  • सेंट में अस्थायी डालें

• जबकि st> 1 का आकार −

  . करें

  • सेंट से तत्व हटाएं

• वापसी (यदि st खाली है, तो NULL, अन्यथा st का शीर्ष तत्व)

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
   public:
   int val;
   TreeNode *left, *right;
   TreeNode(int data){
      val = data;
      left = NULL;
      right = NULL;
   }
};
void inord(TreeNode *root){
   if(root != NULL){
      inord(root->left);
      cout << root->val << " ";
      inord(root->right);
   }
}
class Solution {
   public:
   TreeNode* recoverFromPreorder(string S) {
      stack<TreeNode*> st;
      int i = 0;
      int n = S.size();
      int lvl = 0;
      int num = 0;
      while (i < n) {
         for (lvl = 0; S[i] == '-'; lvl++, i++)
         ;
         num = 0;
         while (i < n && S[i] != '-') {
            num = num * 10 + (S[i] - '0');
            i++;
         }
         while (st.size() > lvl)
         st.pop();
         TreeNode* temp = new TreeNode(num);
         if (!st.empty() && !st.top()->left) {
            st.top()->left = temp;
         }
         else if (!st.empty()) {
            st.top()->right = temp;
         }
         st.push(temp);
      }
      while (st.size() > 1)
      st.pop();
      return st.empty() ? NULL : st.top();
   }
};
main(){
   Solution ob;
   TreeNode *root = ob.recoverFromPreorder("1-2--3--4-5--6--7");
   inord(root);
}

इनपुट

"1-2--3--4-5--6--7"

आउटपुट

3 2 4 1 6 5 7