Post Order Tree Traversal

You get the root of a binary tree. Return a list of its node values in postorder.

In postorder, each node comes after its two subtrees. Its left subtree comes first. Then comes its right subtree. The node itself comes last.

Trees are written level by level, from top to bottom and left to right. A None marks a missing child.

Example 1:

Input: [5,3,8,1,4,None,9]
     5
    / \
   3   8
  / \   \
 1   4   9

Output: [1,4,3,9,8,5]

Example 2:

Input: [9,6,None,None,2]
     9
    /
   6
    \
     2

Output: [2,6,9]
Explanation: Each node here has only one child.
The child still comes before its parent.

Example 3:

Input: [7]
Output: [7]

Constraints:

• 1 to 1,000 nodes.
• Each value is a whole number from 1 to 1,000.
• No two nodes have the same value.

Follow up: The recursive version is only a few lines. Can you also write it without recursion, with your own stack?