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?
// OJ: https://leetcode.com/problems/n-ary-tree-preorder-traversal/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(logN)
class Solution {
private:
vector<int> ans;
void rec(Node *root) {
if (!root) return;
ans.push_back(root->val);
for (auto ch : root->children) rec(ch);
}
public:
vector<int> preorder(Node* root) {
rec(root);
return ans;
}
};
// OJ: https://leetcode.com/problems/n-ary-tree-preorder-traversal/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(logN)
class Solution {
public:
vector<int> preorder(Node* root) {
if (!root) return {};
vector<int> ans;
stack<Node*> s;
s.push(root);
while (s.size()) {
root = s.top();
s.pop();
ans.push_back(root->val);
for (int i = root->children.size() - 1; i >= 0; --i) {
if (root->children[i]) s.push(root->children[i]);
}
}
return ans;
}
};