590. N-ary Tree Postorder Traversal

https://leetcode.com/problems/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]

Example 2:

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [2,6,14,11,7,3,12,8,4,13,9,10,5,1]

Constraints:

• The height of the n-ary tree is less than or equal to 1000
• The total number of nodes is between [0, 10^4]

-----

Intuition

Post order definition => Process the children first, and parent node after. 

In recursive calls, we call into the child functions, and process the current node after called functions return. To preserve the state of function call stack, we need Stack - explicit one.

Our objective is to construct a Stack which has nodes from root to leave stacked - mimicking the function call stack

We push root into stack 1

While stack1 is not empty

Pop elements from stack 1

Do not process (add to ans) yet -  We still need to keep them somewhere to process later * -- push it into another stack2,

Process the children first -- push to same stack 1

In the end we pop elements from stack 2 - which is the same as process child elements before parent in the right order

---

Time - O(n)

Space - O(n)

-----

Followup - Implement without using additional stack

LinkedList has addFirst method which adds element to beginning of list.
We can use addFirst method instead of stack to keep elements in right order