ধরুন একটি বাইনারি গাছ আছে৷ আমরা একটি বাইনারি গাছের মূলে একটি প্রি-অর্ডার গভীরতা প্রথম অনুসন্ধান চালাব।
এই ট্রাভার্সালের প্রতিটি নোডে, আউটপুট হবে D সংখ্যার ড্যাশ (এখানে D এই নোডের গভীরতা), তারপরে আমরা এই নোডের মান প্রদর্শন করি। আমরা জানি যদি একটি নোডের গভীরতা D হয়, তার অবিলম্বে সন্তানের গভীরতা হল D+1 এবং রুট নোডের গভীরতা হল 0৷
আরেকটি বিষয় আমাদের মনে রাখতে হবে যে যদি একটি নোডের একটি মাত্র সন্তান থাকে তবে সেই শিশুটি বাম সন্তান হওয়ার নিশ্চয়তা। সুতরাং, যদি এই ট্রাভার্সালের আউটপুট S দেওয়া হয়, তাহলে গাছটি পুনরুদ্ধার করুন এবং এর মূল ফিরিয়ে দিন।
সুতরাং, যদি ইনপুট হয় "1-2--3--4-5--6--7", তাহলে আউটপুট হবে
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি স্ট্যাক স্ট্যাক সংজ্ঞায়িত করুন
-
i :=0, n :=S
এর আকার -
lvl :=0, সংখ্যা :=0
-
যখন i
-
lvl আরম্ভ করার জন্য :=0, যখন S[i] '-' এর মতো হয়, আপডেট করুন (lvl 1 দ্বারা বৃদ্ধি করুন), (i 1 দ্বারা বৃদ্ধি করুন), করুন −
-
কিছুই করবেন না
-
-
সংখ্যা :=0
-
যখন (i
করুন -
সংখ্যা :=সংখ্যা * 10 + (S[i] - '0')
-
(i 1 দ্বারা বাড়ান)
-
-
যখন st> lvl এর আকার, −
করুন-
st
থেকে উপাদান মুছুন
-
-
temp =সংখ্যা মান সহ একটি নতুন ট্রি নোড তৈরি করুন
-
যদি st খালি না হয় এবং st এর উপরের উপাদানটির বাম না থাকে তাহলে −
-
st :=temp
এর উপরের উপাদানের বাম
-
-
অন্যথায় যখন st খালি না থাকে, তখন −
-
st :=temp
এর উপরের উপাদানের ডানদিকে
-
-
st
-এ তাপমাত্রা সন্নিবেশ করান
-
-
যখন st> 1 এর আকার, −
করুন-
st
থেকে উপাদান মুছুন
-
-
প্রত্যাবর্তন (যদি 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
