স্ট্রিং থেকে বাইনারি ট্রি নির্মাণ C++-এ

যদি একটি স্ট্রিং থাকে যেটিতে পরেনথেসিস এবং পূর্ণসংখ্যা রয়েছে, তাহলে আমরা সেটি থেকে একটি বাইনারি ট্রি তৈরি করতে পারি। পুরো ইনপুট একটি বাইনারি ট্রিকে উপস্থাপন করে। এখানে একটি পূর্ণসংখ্যা থাকে যা শূন্য, এক বা দুটি জোড়া পরেনথেসিস দ্বারা অনুসরণ করা হয়। পূর্ণসংখ্যাটি রুটের মান উপস্থাপন করে এবং একটি জোড়া পরেনথেসিস একই কাঠামোর একটি চাইল্ড বাইনারি ট্রি ধারণ করে।

উদাহরণ

ইনপুট: "4(2(3)(1))(6(5))"

আউটপুট (ইনঅর্ডার ট্রাভার্সাল): [3, 2, 1, 4, 5, 6]

অ্যালগরিদম

1. solve() ফাংশন ডিফাইন করুন যা স্ট্রিং s এবং ইনডেক্স idx নেবে।
2. যদি idx >= s.size() হয়, তবে NULL রিটার্ন করুন।
3. একটি খালি স্ট্রিং num ডিক্লেয়ার করুন।
4. যতক্ষণ idx < s.size() এবং s[idx] '(' বা ')' নয়, ততক্ষণ num-এ ক্যারেক্টার যোগ করুন এবং idx বাড়ান।
5. num মানով একটি নতুন নোড তৈরি করুন।
6. যদি idx < s.size() এবং s[idx] == '(' হয়:
   • idx বাড়ান।
   • নোডের বাম চাইল্ড = solve(s, idx)।
   • idx বাড়ান।
   • যদি আবার s[idx] == '(' হয়, তবে ডান চাইল্ডও একইভাবে তৈরি করুন।
7. নোড রিটার্ন করুন।
8. মেইন মেথড থেকে idx = 0 দিয়ে solve(s, idx) কল করুন।

C++ কোড উদাহরণ

#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* solve(string s, int& idx) {
        if (idx >= s.size()) return NULL;
        string num = "";
        while (idx < s.size() && s[idx] != '(' && s[idx] != ')') {
            num += s[idx];
            idx++;
        }
        TreeNode* node = new TreeNode(stoi(num));
        if (idx < s.size() && s[idx] == '(') {
            idx++;
            node->left = solve(s, idx);
            idx++;
            if (idx < s.size() && s[idx] == '(') {
                idx++;
                node->right = solve(s, idx);
                idx++;
            }
        }
        return node;
    }
    TreeNode* str2tree(string s) {
        int idx = 0;
        return solve(s, idx);
    }
};

int main() {
    Solution ob;
    TreeNode *root = ob.str2tree("4(2(3)(1))(6(5))");
    inord(root);
    return 0;
}

ইনপুট

"4(2(3)(1))(6(5))"

আউটপুট

3 2 1 4 5 6