文章作者：Tyan
博客：noahsnail.com | CSDN | 简书
1. Description
N-ary Tree Postorder Traversal
2. Solution
- Recursive
/*
// 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> postorder(Node* root) {
vector<int> result;
if(!root) {
return result;
}
postOrderTraverse(result, root);
return result;
}
void postOrderTraverse(vector<int>& result, Node* root) {
if(!root) {
return;
}
int size = root->children.size();
for(int i = 0; i < size; i++) {
postOrderTraverse(result, root->children[i]);
}
result.push_back(root->val);
}
};
- Iterative
/*
// 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> postorder(Node* root) {
vector<int> result;
if(!root) {
return result;
}
postOrderTraverse(result, root);
return result;
}
void postOrderTraverse(vector<int>& result, Node* root) {
stack<Node*> list;
list.push(root);
while(!list.empty()) {
Node* current = list.top();
list.pop();
int size = current->children.size();
for(int i = 0; i < size; i++) {
list.push(current->children[i]);
}
result.push_back(current->val);
}
reverse(result.begin(), result.end());
}
};
