给定一个 N 叉树，返回其节点值的 后序遍历 。
N 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。
进阶：递归法很简单，你可以使用迭代法完成此题吗?
示例 ：
590.png输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[2,6,14,11,7,3,12,8,4,13,9,10,5,1]
- N叉树的数据结构定义如下，节点中包含多个子节点组成的vector数组。
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val) {
val = _val;
}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
- 递归算法
递归算法理解起来比较简单，在遍历根节点时，首先递归遍历其子节点，最后遍历根节点。
void innerPostOrder(Node *root, vector<int> &vec) {
if (root == nullptr) {
return;
}
for (int i = 0; i < root->children.size(); ++i) {
innerPostOrder(root->children[i], vec);
}
vec.push_back(root->val);
}
- 迭代算法
按照N叉树后序遍历的具体算法执行过程，访问某个节点时，首先访问其子节点，最后才访问根节点。所以，我们想到需要使用堆栈保存根节点。
进栈： 首次访问节点时，push进栈，并将其子节点也一并进栈。
出栈： 当某个节点是叶子节点（没有子节点）时需要出栈。
非叶子节点出栈：需要判断其所有子节点都已被访问，我们定义一个临时指针，保存上次出栈的节点。当上一个出栈节点为其最后一个子节点，那么就可以继续对非叶子节点进行出栈操作。
void stackPostOrder(Node *root, vector<int> &vec) {
if (root == nullptr) {
return;
}
stack<Node *> st;
st.push(root);
Node *last = nullptr;
while (!st.empty()) {
Node *p = st.top();
int size = p->children.size();
if (size == 0 || p->children[size - 1] == last) {
vec.push_back(p->val);
last = p;
st.pop();
continue;
}
for (int i = size; i > 0; --i) {
st.push(p->children[i - 1]);
}
}
}
- 完整实现如下
class Solution {
public:
vector<int> postorder(Node* root) {
vector<int> ret;
// innerPostOrder(root, ret);
stackPostOrder(root, ret);
return ret;
}
void innerPostOrder(Node *root, vector<int> &vec) {
if (root == nullptr) {
return;
}
for (int i = 0; i < root->children.size(); ++i) {
innerPostOrder(root->children[i], vec);
}
vec.push_back(root->val);
}
void stackPostOrder(Node *root, vector<int> &vec) {
if (root == nullptr) {
return;
}
stack<Node *> st;
st.push(root);
Node *last = nullptr;
while (!st.empty()) {
Node *p = st.top();
int size = p->children.size();
if (size == 0 || p->children[size - 1] == last) {
vec.push_back(p->val);
last = p;
st.pop();
continue;
}
for (int i = size; i > 0; --i) {
st.push(p->children[i - 1]);
}
}
}
};
