समस्या विवरण
मान लीजिए हमारे पास एक N-ary ट्री है, हमें इसके नोड्स का प्रीऑर्डर ट्रैवर्सल ज्ञात करना है।
उदाहरण
यदि इनपुट ट्री है:
तो आउटपुट होगा: [1,3,5,6,2,4]
हल करने का दृष्टिकोण
इस समस्या को हल करने के लिए निम्नलिखित चरणों का पालन करें:
- एक सरणी ans परिभाषित करें
- preorder() नामक एक विधि परिभाषित करें, जो रूट लेती है
- यदि रूट null है, तो खाली सूची लौटाएं
- रूट के मान को ans के अंत में डालें
- रूट के चिल्ड्रन सरणी में प्रत्येक चाइल्ड i के लिए:
- preorder(i) कॉल करें
- ans लौटाएं
C++ कार्यान्वयन
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v) {
cout << "[";
for(int i = 0; i < v.size(); i++) {
cout << v[i] << ", ";
}
cout << "]" << endl;
}
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val) { val = _val; }
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
class Solution {
public:
vector<int> ans;
vector<int> preorder(Node* root) {
if (!root)
return {};
ans.emplace_back(root->val);
for (auto i : root->children)
preorder(i);
return ans;
}
};
int main() {
Solution ob;
Node *node5 = new Node(5), *node6 = new Node(6);
vector<Node*> child_of_3 = {node5, node6};
Node* node3 = new Node(3, child_of_3);
Node *node2 = new Node(2), *node4 = new Node(4);
vector<Node*> child_of_1 = {node3, node2, node4};
Node *node1 = new Node(1, child_of_1);
print_vector(ob.preorder(node1));
return 0;
}
इनपुट
Node *node5 = new Node(5), *node6 = new Node(6); vector<Node*> child_of_3 = {node5, node6}; Node* node3 = new Node(3, child_of_3); Node *node2 = new Node(2), *node4 = new Node(4); vector<Node*> child_of_1 = {node3, node2, node4}; Node *node1 = new Node(1, child_of_1);
आउटपुट
[1, 3, 5, 6, 2, 4, ]
