N-ary Tree Postorder Traversal

An iterative solution avoids recursion and the risk of stack overflow. A common and elegant iterative technique for postorder traversal involves using a single stack and modifying the preorder traversal logic. The standard preorder traversal is (Root, Left, Right). We can modify it to (Root, Right, Left) and then reverse the result to get (Left, Right, Root), which is the postorder traversal.

• Initialize an empty LinkedList<Integer> named result and an empty Stack<Node> named stack.
• If root is null, return the empty result.
• Push the root node onto the stack.
• Loop while the stack is not empty:

• Pop a node, `current`, from the `stack`.
  

• Add `current.val` to the *front* of the `result` list.
  

• Iterate through the children of `current` from left to right and push each `child` onto the `stack`.
  

• Return the result list.

For an N-ary tree, the modified preorder traversal becomes (Root, Last Child, ..., First Child).

• We initialize a stack and push the root node onto it.
• We also initialize a LinkedList for our result. Using a LinkedList allows for efficient O(1) additions to the front.
• We loop as long as the stack is not empty. In each iteration:
  1. We pop a node from the stack.
  2. We add this node's value to the front of our result list. This is the key step that achieves the reversal.
  3. We then iterate through the children of the popped node (from left to right) and push them onto the stack. Because the stack is a LIFO (Last-In, First-Out) structure, the last child pushed (the rightmost one) will be on top and will be processed next.
• This process effectively traverses the tree in the order of Root, Child_N, ..., Child_1 and builds the result list in reverse, yielding the correct postorder sequence Child_1, ..., Child_N, Root.

/*
// 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) {
        LinkedList<Integer> result = new LinkedList<>();
        if (root == null) {
            return result;
        }

        Stack<Node> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            Node node = stack.pop();
            // Add to the front of the list
            result.addFirst(node.val);

            // Push children from left to right, so they are processed from right to left
            for (Node child : node.children) {
                stack.push(child);
            }
        }
        return result;
    }
}

If using an ArrayList, you would add to the end and then reverse the entire list once at the end using Collections.reverse(result). Adding to the front of a LinkedList is generally more efficient.