मान लीजिए हमारे पास एक स्ट्रिंग है जिसमें पैरेंथेसिस और पूर्णांक हैं। हमें उस स्ट्रिंग से एक बाइनरी ट्री का निर्माण करना है। पूरा इनपुट एक बाइनरी ट्री को दर्शाता है। इसमें एक पूर्णांक होता है जिसके बाद शून्य, एक या दो जोड़े पैरेंथेसिस होते हैं। पूर्णांक रूट का मान दर्शाता है और पैरेंथेसिस का एक जोड़ा उसी संरचना के साथ एक चाइल्ड बाइनरी ट्री को दर्शाता है।
उदाहरण के लिए, यदि इनपुट "4(2(3)(1))(6(5))" है, तो आउटपुट [3,2,1,4,5,6] होगा (इनऑर्डर ट्रैवर्सल)।
समाधान दृष्टिकोण
इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:
solve()फ़ंक्शन परिभाषित करें, जोs(स्ट्रिंग) औरidx(इंडेक्स) लेता है।- यदि
idx >= s.size()है, तोNULLवापस करें। - एक खाली स्ट्रिंग
numबनाएं। - जब तक
idx < s.size()औरs[idx]न तो'('है और न ही')', तब तकnumमें कैरेक्टर जोड़ें औरidxबढ़ाएं। numमान से एक नया नोड बनाएं।- यदि
idx < s.size()औरs[idx] == '('है, तो:idxबढ़ाएं।- नोड का लेफ्ट चाइल्ड =
solve(s, idx)। idxबढ़ाएं।- यदि फिर से
s[idx] == '('है, तो:idxबढ़ाएं।- नोड का राइट चाइल्ड =
solve(s, idx)। idxबढ़ाएं।
- नोड वापस करें।
- मेन मेथड में:
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;
TreeNode* temp = new TreeNode(-1);
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
