给定一个 N 叉树，返回其节点值的后序遍历。
例如，给定一个 3叉树 :
narytreeexample.png
返回其后序遍历: [5,6,3,2,4,1].
说明: 递归法很简单，你可以使用迭代法完成此题吗?
题解：此题与589同源，589是前序，故先入根节点，590后序最后入根节点即可。
/*
// 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 {
public List<Integer> postorder(Node root) {
List<Integer>ans = new ArrayList<>();
if(root == null)
return ans;
post(root,ans);
return ans;
}
public void post(Node root,List<Integer>ans){
if (root == null)
return;
for(Node node : root.children){
post(node,ans);
}
ans.add(root.val);
}
}
2.迭代：
public List<Integer> postorder2(Node root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
//前指针
Node pre = null;
Stack<Node> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
Node cur = stack.peek();
if ((cur.children.size() == 0) || (pre != null && cur.children.contains(pre))) {
//加入结果集
res.add(cur.val);
stack.pop();
//更新pre指针
pre = cur;
} else {
//继续压栈，注意压栈是从右往左
List<Node> nodeList = cur.children;
for (int i = nodeList.size() - 1; i >= 0; i--) {
stack.push(nodeList.get(i));
}
}
}
return res;
}
