145. Binary Tree Postorder Traversal
You receive root, the top node of a binary tree (possibly null for an empty tree). Each node has an integer val plus left and right child pointers. Return the tree's postorder traversal as a list of values: everything in the node's left subtree first, then everything in its right subtree, and the node itself last.
For input purposes the tree is written in level order with the word null marking a missing child — for example 1 2 3 null 4 is a root 1 whose left child 2 has only a right child 4, and whose right child is 3.
Postorder is the order in which you can safely delete a tree or compute a value that depends on both children. The recursive version is trivial; the iterative one is famously the trickiest of the three depth-first orders — though a well-known reversal trick sidesteps most of the pain.
Example 1:
Input: root = [1, null, 2, 3]
Output: [3, 2, 1]
Explanation: The left subtree of 1 is empty; the right subtree yields its own left child 3 first, then 2; the root 1 comes last.
Example 2:
Input: root = [1, 2, 3, 4, 5, null, 6]
Output: [4, 5, 2, 6, 3, 1]
Explanation: Left subtree of 1: children 4 and 5 before their parent 2. Right subtree: 6 before its parent 3. The root 1 is recorded last.
Constraints:
- 0 ≤ number of nodes ≤ 100
- -100 ≤ Node.val ≤ 100
Hints:
Recursively: finish the left subtree, finish the right subtree, then append the node. The base case is a null child.
Iteratively, notice that postorder (left, right, node) read backwards is (node, right, left) — a preorder that explores right before left. Produce that with a stack (push left before right, so right pops first), then reverse the collected values once at the end.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [1, null, 2, 3]
Expected output: [3, 2, 1]