=> reverse ( use linkedList addFirst(), 注意要用這個要頭尾都宣告純 LinkedList<> list = new LinkedList<>() 才會有這個方法
=>得到答案
O(M), O(M) M is the total nodes of this tree
class Solution {
public List<Integer> postorder(Node root) {
// because preorder is root left right
// postorder is left right root
// so root right left then reverse is postorder
// to acheive reverse we can push (addFirst) to LinkedList
LinkedList<Integer> res = new LinkedList<>();
if (root == null) {
return res;
}
Stack<Node> stack = new Stack<>();
stack.add(root);
while (!stack.isEmpty()) {
Node node = stack.pop(); // pop right then left
if (node != null) {
res.addFirst(node.val); // add first, so it would be left right root
for (Node n : node.children) {
stack.push(n); // push left right
}
}
}
return res;
}
}
recursive
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<Integer> postorder(Node root) {
List<Integer> res = new ArrayList<>();
helper(root, res);
return res;
}
private void helper(Node root, List<Integer> res) {
if (root == null) {
return;
}
for (Node node : root.children) {
helper(node, res);
}
res.add(root.val);
}
}
