ধরুন একটি বাইনারি গাছ আছে৷ আমরা একটি বাইনারি গাছের মূলে একটি প্রি-অর্ডার গভীরতা প্রথম অনুসন্ধান চালাব।
এই ট্রাভার্সালের প্রতিটি নোডে, আউটপুট হবে 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