給定一個 N 叉樹，返回其節(jié)點(diǎn)值的后序遍歷酝碳。
例如遂跟，給定一個 3叉樹 :
narytreeexample.png
返回其后序遍歷: [5,6,3,2,4,1].
說明: 遞歸法很簡單蓬推，你可以使用迭代法完成此題嗎?
題解：此題與589同源，589是前序俺抽，故先入根節(jié)點(diǎn)敞映，590后序最后入根節(jié)點(diǎn)即可。
/*
// 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))) {
//加入結(jié)果集
res.add(cur.val);
stack.pop();
//更新pre指針
pre = cur;
} else {
//繼續(xù)壓棧磷斧，注意壓棧是從右往左
List<Node> nodeList = cur.children;
for (int i = nodeList.size() - 1; i >= 0; i--) {
stack.push(nodeList.get(i));
}
}
}
return res;
}
