//1.遞歸
public List<Integer> postorder(Node root) {
List<Integer> list = new ArrayList<Integer>();
if (root == null) return list;
post_order(list,root.children);
list.add(root.val);
return list;
}
public void post_order(List<Integer> list,List<Node> subList) {
if (subList == null || subList.size() == 0) return;
for (Node n : subList) {
if (n == null) return;
post_order(list, n.children);
list.add(n.val);
}
}
//2.疊代
public List<Integer> postorder(Node root) {
LinkedList<Node> input = new LinkedList<>();
LinkedList<Integer> output = new LinkedList<>();
if (root == null) {
return output;
}
input.add(root);
while (!input.isEmpty()) {
Node node = input.pollLast();
output.addFirst(node.val);
if (node.children != null) {
for (Node item : node.children) {
if (item != null) {
input.add(item);
}
}
}
}
return output;
}