मान लीजिए एक बाइनरी ट्री है। हम बाइनरी ट्री की रूट पर एक प्रीऑर्डर डेप्थ फर्स्ट सर्च चलाएंगे।
इस ट्रैवर्सल में प्रत्येक नोड पर, आउटपुट D संख्या में डैश होगा (यहां D इस नोड की गहराई है), उसके बाद हम इस नोड का मान प्रदर्शित करते हैं। जैसा कि हम जानते हैं यदि किसी नोड की गहराई D है, तो उसके तत्काल बच्चे की गहराई D+1 है और रूट नोड की गहराई 0 है।
एक और बात ध्यान रखनी है कि यदि किसी नोड का केवल एक बच्चा है, तो वह बच्चा बायां बच्चा होने की गारंटी है। इसलिए, यदि इस ट्रैवर्सल का आउटपुट S दिया गया है, तो ट्री को पुनर्प्राप्त करें और उसकी रूट लौटाएं।
यदि इनपुट "1-2--3--4-5--6--7" है, तो आउटपुट होगा -
हल करने के चरण
एक स्टैक st परिभाषित करें
i := 0, n := S का आकार
lvl := 0, num := 0
जब तक i < n: डैश गिनकर lvl ज्ञात करें, फिर संख्या पढ़ें
जब तक स्टैक का आकार > lvl: स्टैक से पॉप करें
num मान के साथ नया ट्री नोड बनाएं
यदि स्टैक खाली नहीं है और शीर्ष का बायां बच्चा खाली है तो बायां बच्चा सेट करें, अन्यथा दायां बच्चा सेट करें
नोड को स्टैक में पुश करें
अंत में स्टैक से तब तक पॉप करें जब तक आकार 1 न हो जाए, शीर्ष तत्व लौटाएं
उदाहरण
#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();
}
};
int main() {
Solution ob;
TreeNode *root = ob.recoverFromPreorder("1-2--3--4-5--6--7");
inord(root);
return 0;
}
इनपुट
"1-2--3--4-5--6--7"
आउटपुट
3 2 4 1 6 5 7
