# 145. Binary Tree Postorder Traversal

## Approach 1: Recursive

• Time: $O(n)$
• Space: $O(h)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public: vector postorderTraversal(TreeNode* root) { vector ans; postorder(root, ans); return ans; } private: void postorder(TreeNode* root, vector& ans) { if (root == nullptr) return; postorder(root->left, ans); postorder(root->right, ans); ans.push_back(root->val); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution { public List postorderTraversal(TreeNode root) { List ans = new ArrayList<>(); postorder(root, ans); return ans; } private void postorder(TreeNode root, List ans) { if (root == null) return; postorder(root.left, ans); postorder(root.right, ans); ans.add(root.val); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution: def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]: ans = [] def postorder(root: Optional[TreeNode]) -> None: if not root: return postorder(root.left) postorder(root.right) ans.append(root.val) postorder(root) return ans 

## Approach 2: Iterative

• Time: $O(n)$
• Space: $O(h)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public: vector postorderTraversal(TreeNode* root) { if (root == nullptr) return {}; vector ans; stack stack{{root}}; while (!stack.empty()) { root = stack.top(), stack.pop(); ans.push_back(root->val); if (root->left) stack.push(root->left); if (root->right) stack.push(root->right); } reverse(begin(ans), end(ans)); return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public List postorderTraversal(TreeNode root) { if (root == null) return new ArrayList<>(); List ans = new ArrayList<>(); Deque stack = new ArrayDeque<>(); stack.push(root); while (!stack.isEmpty()) { root = stack.pop(); ans.add(root.val); if (root.left != null) stack.push(root.left); if (root.right != null) stack.push(root.right); } Collections.reverse(ans); return ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution: def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]: if not root: return [] ans = [] stack = [root] while stack: node = stack.pop() ans.append(node.val) if node.left: stack.append(node.left) if node.right: stack.append(node.right) return ans[::-1]