共计 1527 个字符，预计需要花费 4 分钟才能阅读完成。
题目
Given an n-ary tree, return the postorder traversal of its nodes’ values.
For example, given a 3-ary tree:
Return its postorder traversal as: [5,6,3,2,4,1].
Note:
Recursive solution is trivial, could you do it iteratively?
题目地址
讲解
这道题跟先序遍历差不多，调换一下添加结点的顺序而已。参考：leetcode 讲解 –589. N-ary Tree Preorder Traversal
但这道题的迭代解法稍微有点麻烦，需要一个标记，初次访问一个结点的时候我们并不能立即将它的值加进结果里，而是要等它的所有孩子访问完毕再加。也就是说我们第一次访问它并不 pop，第二次访问它才 pop。
Java 代码
递归解法：
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val,List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
private List<Integer> result = new ArrayList<>();
public List<Integer> postorder(Node root) {
if(root==null){
return result;
}
for(Node node:root.children){
postorder(node);
}
result.add(root.val);
return result;
}
}
迭代解法：
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val,List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
private List<Integer> result = new ArrayList<>();
private Stack<Bundle> stack = new Stack<>();
private Stack<Bundle> stack_temp = new Stack();
public List<Integer> postorder(Node root) {
if(root==null){
return result;
}
Bundle rootBundle = new Bundle(root);
stack.push(rootBundle);
while(!stack.empty()){
Bundle bundle = stack.peek();
if(bundle.flag){
result.add(stack.pop().node.val);
continue;
}
for(Node node:bundle.node.children){
Bundle d = new Bundle(node);
stack_temp.push(d);
}
while(!stack_temp.empty()){
stack.push(stack_temp.pop());
}
bundle.flag = true;
}
return result;
}
class Bundle{
Node node;
Boolean flag;
public Bundle(Node node){
flag = false;
this.node = node;
}
}
}
