সি++-এ প্রি-অর্ডার ট্রভারসাল থেকে ট্রি রিকভার করা

মান লিইয়ে নিই একটি বাইনারি ট্রি রয়েছে। আমরা রুট থেকে একটি প্রি-অর্ডার ডেপথ ফার্স্ট সার্চ চালাব।

এই ট্রভারসালের প্রতিটি নোডে, আউটপুট হবে 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 := 0 থেকে आरंभ করুন, যখন S[i] '-' এর সমান, আপডেট করুন (lvl 1 বাড়ান), (i 1 বাড়ান), করুন:
    • কিছুই করবেন না
  • num := 0
  • যতক্ষণ (i < n এবং S[i] '-' এর সমান নয়), করুন:
    • num := num * 10 + (S[i] - '0')
    • (i 1 বাড়ান)
  • যতক্ষণ st-এর আকার > lvl, করুন:
    • st থেকে উপাদান মুছুন
  • temp = num মান দিয়ে একটি নতুন Tree Node তৈরি করুন
  • যদি st খালি না হয় এবং st-এর টপ এলিমেন্টের বাম নাল না হয়, তবে:
    • st-এর টপ এলিমেন্টের বাম := temp
  • অন্যথায় যদি st খালি না হয়, তবে:
    • st-এর টপ এলিমেন্টের ডান := temp
  • 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