Binary Tree Postorder Traversal
Problem Description
Given the root of a binary tree, return the postorder traversal of its nodes' values.
Example 1:
Output: [3,2,1]
Example 2:
Output: [4,6,7,5,2,9,8,3,1]
Example 3:
Input: root = []
Output: []
Example 4:
Input: root = [1]
Output: [1]
Constraints:
- The number of the nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
Follow up: Recursive solution is trivial, could you do it iteratively?
Solve it on LeetCode
Approaches
1. Recursive Approach
Intuition:
The simplest way to perform a postorder traversal on a binary tree is by using recursion. The nature of postorder traversal is to access children nodes before their parent nodes (Left-Right-Root). Recursion naturally takes care of this backtracking for us.
Code:
- Time Complexity: O(N), where N is the number of nodes in the tree.
- Space Complexity: O(N) due to the recursion call stack.
2. Iterative Approach using Two Stacks
Intuition:
The iterative approach using two stacks mimics the recursive postorder traversal process by using stacks to explore nodes. We can push nodes into the first stack to manage depth, and the second stack to reverse the traversal order temporarily.
Code:
- Time Complexity: O(N), because we process each node twice (pushed into two stacks).
- Space Complexity: O(N) due to the extra space used by the two stacks.
3. Iterative Approach with One Stack
Intuition:
Using one stack to mimic the backtracking operations needed for postorder traversal is more efficient. We need to keep track of previously visited nodes to correctly process the right subtrees after finishing the left subtrees.
Code:
- Time Complexity: O(N), since each node is visited exactly once.
- Space Complexity: O(N) in the worst case, elements in the stack might be as large as the height of the tree.