একটি N-ary ট্রি দেওয়া থাকলে, তার নোডগুলোর প্রি-অর্ডার ট্রভার্সাল বের করতে হবে। প্রি-অর্ডারে প্রথমে রুট নোড, তারপর বাম থেকে ডানে সন্তান নোডগুলো ভিজিট করা হয়।
উদাহরণস্বরূপ, নিচের ট্রির জন্য আউটপুট হবে [1,3,5,6,2,4]:
সমাধানের ধাপসমূহ
- একটি অ্যারে ans সংজ্ঞায়িত করুন।
- preorder() মেথড তৈরি করুন যা রুট নোড নেয়।
- যদি রুট null হয়, তবে খালি লিস্ট রিটার্ন করুন।
- রুটের মান ans-এ যোগ করুন।
- রুটের প্রতিটি সন্তান নোডের জন্য পুনরাবৃত্তিমূলকভাবে preorder() কল করুন।
- ans রিটার্ন করুন।
C++ কোড উদাহরণ
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> 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, ]
