LeetCode #145 Binary Tree Postorder Traversal

Hard

Problem

Given a binary tree, return the postorder traversal of its nodes’ values.

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3
Output: [3,2,1]

Follow up: Recursive solution is trivial, could you do it iteratively?

Solution — Recursion

As problem describes, it’s trivial.

Complexity

It’s trivial that time complexity will be O(n) which n denotes to counts of node of this tree.

For space complexity, because we need h calls for reaching leaves if h denotes to path length of the longest path in this tree. Hence, space complexity is O(h). Or you can say O(logn) because h is bounded by logn.

Solution — Iteration

It’s not easy if we’d like to traverse with postorder iteratively. However, by following concepts we can achieve it:

1. From root, put possible right child and root into a stack, and go down to left child as new root until root be null.
2. Pop an element from stack. If we found that its right child haven’t been handled, handle its right child first by popping right child out and pushing this element back. Or, print value of current element.
3. Repeat 1 and 2 until no element should be handled.

Complexity

For each node, it may be at most push/pop twice in entire processing. Hence the time complexity is O(2n) = O(n). And because the stack should have ability to save the longest path from root to leaves of this tree. It’s space complexity is O(h) (or O(logn)) if h denotes to count of nodes if that longest path.