【leetcode】589. N-ary Tree Preorder Traversal
题目：
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?
1. Recursive solution:
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public:
vector<int> preorder(Node* root) {
vector<int> order = {};
if (root) {
traversal(root, order);
}
return order;
}
void traversal(Node* root, vector<int> &order) {
order.push_back(root->val);
int num = root->children.size();
for (int i = 0; i < num; i++) {
traversal(root->children.at(i), order);
}
}
};
2. Iterative solution:
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public:
vector<int> preorder(Node* root) {
vector<int> order = {};
stack<Node*> nodeStack;
if (root) {
nodeStack.push(root);
}
while (!nodeStack.empty()) {
Node* node = nodeStack.top();
nodeStack.pop();
order.push_back(node->val);
int num = node->children.size();
for (int i = num - 1; i >= 0; i--) {
nodeStack.push(node->children.at(i));
}
}
return order;
}
};