145. Binary Tree Postorder Traversal
3 min readNov 3, 2021
Given the root
of a binary tree, return the postorder traversal of its nodes' values.
Example 1:
Input: root = [1,null,2,3]
Output: [3,2,1]
Example 2:
Input: root = []
Output: []
Example 3:
Input: root = [1]
Output: [1]
Example 4:
Input: root = [1,2]
Output: [2,1]
Example 5:
Input: root = [1,null,2]
Output: [2,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?
Solution 1: Recursive
- Recursively traverse the left subtree.
- Recursively traverse the right subtree.
- Store the root element.
class Solution {
public void traversal(TreeNode root, List<Integer> ans) {
if (root == null)
return;
if (root.left != null)
traversal(root.left, ans);
if (root.right != null)
traversal(root.right, ans);
ans.add(root.val);}
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<Integer>();
traversal(root, ans);
return ans;
}
}
Time Complexity: O(N)
Auxiliary Space: O(H), where H is the height of the tree.
Solution 2: Iterative — Using 2 stacks
- Create 2 stacks of TreeNode, push root Node to stack1.
- Do the following till stack1 is not empty:
- Pop a Node from the stack and push it to stack2.
- If the left child is not null, push it to the stack1.
- If the right child is not null, push it to the stack1.
- Iterate over stack2 and add the current node value to the list.
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<Integer>();
if (root == null)
return ans;
Stack<TreeNode> stack1 = new Stack<>();
Stack<TreeNode> stack2 = new Stack<>();stack1.push(root);
while (!stack1.isEmpty()) {
TreeNode current = stack1.pop();
stack2.push(current);
if (current.left != null)
stack1.push(current.left);
if (current.right != null)
stack1.push(current.right);
}
while (!stack2.isEmpty()) {
TreeNode current = stack2.pop();
ans.add(current.val);
}
return ans;
}
}
Time Complexity: O(N)
Space: O(H), where H is the height of the tree.
Solution 3: Iterative — Using 1 stack
- Create a stack of TreeNode and push root to it.
- Do the following till stack is not empty:
- Pop a Node from the stack and add it to the start of list(ans), use linked list.
- If the left child is not null, push it to the stack.
- If the right child is not null, push it to the stack.
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> ans = new LinkedList<Integer>();
if (root == null)
return ans;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode current = stack.pop();
ans.addFirst(current.val);
if (current.left != null)
stack.push(current.left);
if (current.right != null)
stack.push(current.right);
}
return ans;
}
}
Time Complexity: O(N)
Space: O(H), where H is the height of the tree.