590. N-ary Tree Postorder Traversal

/**

 * 590. N-ary Tree Postorder Traversal

 * Given an n-ary tree, return the postorder traversal of its nodes’ values.

 *

 * Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

 *

 * Follow up:

 *

 * Recursive solution is trivial, could you do it iteratively?

 *

 * Example 1:

 *

 * Input: root = [1,null,3,2,4,null,5,6]

 * Output: [5,6,3,2,4,1]

 */

See the solution on github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/n_array/PostOrder.java

Observation: Here is a simple iterative solution. You leverage a stack where you begin traversing the tree from the root. You use a stack since stack will have the last element processed on top. As you pop the element off the stack you add the elements at beginning of the output list since you have already processed the children. For each element popped off the stack you add all its children to the list. Need to add children from left to right such that right most element is on top of stack.

Here is the code:

public List<Integer> postorder(Node root) {
    LinkedList<Integer> list = new LinkedList<>();
    if (root == null) {
        return list;
    }
    Stack<Node> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        Node n = stack.pop();
        //stack.addAll will make the right most child on top while is what we want
        stack.addAll(n.children);
        //add the newly processed val into the beginning of the list
        list.addFirst(n.val);
    }
    return list;
}