Sponsored
Sponsored
This approach leverages the simplicity of recursion to perform a preorder traversal on an n-ary tree. We start at the root node, then recursively process each child's subtree.
Time Complexity: O(n), where n is the number of nodes in the tree, since we visit each node once.
Space Complexity: O(n) for the recursion stack used in the helper function.
1#include <vector>
2using namespace std;
3
4class Node {
5public:
6 int val;
7 vector<Node*> children;
8
9 Node() {}
10
11 Node(int _val) {
12 val = _val;
13 }
14
15 Node(int _val, vector<Node*> _children) {
16 val = _val;
17 children = _children;
18 }
19};
20
21class Solution {
22public:
23 void preorderHelper(Node* node, vector<int>& result) {
24 if (!node) return;
25 result.push_back(node->val);
26 for (Node* child : node->children) {
27 preorderHelper(child, result);
28 }
29 }
30
31 vector<int> preorder(Node* root) {
32 vector<int> result;
33 preorderHelper(root, result);
34 return result;
35 }
36};In C++, the solution uses a preorderHelper function that recursively visits and stores each node's value in a vector named result. This vector is constructed and returned by the preorder function, giving the required preorder traversal.
This approach uses an explicit stack to simulate the call stack of recursion. We manually manage traversals seen in recursion, starting from the root node, iteratively processing each node, then adding each child to a stack for future visits.
Time Complexity: O(n). Space Complexity: O(n), as most nodes can be stored in the stack in the worst case.
1
This C solution uses a stack structure to handle the iterative traversal. The stack manually manages nodes left to process, with each node added to the result upon visitation. It handles children in reverse order to maintain correct preorder evaluation.