Problem

Given an n-ary tree, return the preorder traversal of its nodes’ values.

For example, given a 3-ary tree:

Return its preorder traversal as: [1,3,5,6,2,4].

Note: Recursive solution is trivial, could you do it iteratively?

Solution1: Recursive

// Author: Huahua

// Running time: 48 ms

class Solution {

public:

vector<int> preorder(Node* root) {

vector<int> ans;

preorder(root, ans);

return ans;

}

private:

void preorder(Node* root, vector<int>& ans) {

if (!root) return;

ans.push_back(root->val);

for (const auto& child : root->children)

preorder(child, ans);

}

};

// Author: Huahua

// Running time: 52 ms

class Solution {

public:

vector<int> preorder(Node* root) {

if (!root) return {};

vector<int> ans;

stack<Node*> s;

s.push(root);

while (!s.empty()) {

const Node* node = s.top(); s.pop();

ans.push_back(node->val);

for (auto it = node->children.rbegin(); it != node->children.rend(); ++it)

s.push(*it);

}

return ans;

}

};