Problem Statement:
Given the root of a binary tree, return the postorder traversal of its nodes’ values..
Examples:
Example 1:
Input: root = [1,null,2,3]
Output: [3,2,1]
Explanation:
Example 2:
Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]
Output: [4,6,7,5,2,9,8,3,1]
Explanation:
Example 3:
Input: root = []
Output: []
Example 4:
Input: root = [1]
Output: [1]
Constraints:
- The number of nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
Approach
- Use two stacks:
s1for processing nodes ands2for storing them in reverse postorder. - Push root to
s1. - While
s1is not empty:- Pop from
s1, push tos2. - Push left child (if any) to
s1. - Push right child (if any) to
s1.
- Pop from
- After processing, pop from s2 and store node values in ans (this gives postorder).
Time Complexity:
Time Complexity = O(n)
Space Complexity:
Space Complexity = O(n)
Dry Run
Input: root = [1, 2, 3, null, 4]
Tree Structure:
1
/ \
2 3
\
4
Initialize:
s1 = [1]
s2 = []
ans = []
--- First While Loop (s1 not empty) ---
Pop 1 from s1 → curr = 1
Push 1 to s2 → s2 = [1]
Push 2 to s1 → s1 = [2]
Push 3 to s1 → s1 = [2, 3]
Pop 3 from s1 → curr = 3
Push 3 to s2 → s2 = [1, 3]
(No children to push)
Pop 2 from s1 → curr = 2
Push 2 to s2 → s2 = [1, 3, 2]
Push 4 to s1 → s1 = [4]
Pop 4 from s1 → curr = 4
Push 4 to s2 → s2 = [1, 3, 2, 4]
(No children to push)
--- Second While Loop (s2 not empty) ---
Pop 4 from s2 → ans = [4]
Pop 2 from s2 → ans = [4, 2]
Pop 3 from s2 → ans = [4, 2, 3]
Pop 1 from s2 → ans = [4, 2, 3, 1]
Traversal complete.
Final ans (postorder) = [4, 2, 3, 1]
Output: Result: [4, 2, 3, 1]
var postorderTraversal = function(root) {
if(!root) return [];
let s1 = [root];
let s2 = [];
while(s1.length) {
let curr = s1.pop();
s2.push(curr);
curr.left && s1.push(curr.left);
curr.right && s1.push(curr.right);
}
let ans = [];
while(s2.length) {
ans.push(s2.pop().val);
}
return ans;
};
def postorderTraversal(root):
if not root:
return []
s1 = [root]
s2 = []
while s1:
curr = s1.pop()
s2.append(curr)
if curr.left:
s1.append(curr.left)
if curr.right:
s1.append(curr.right)
ans = []
while s2:
ans.append(s2.pop().val)
return ans
public List postorderTraversal(TreeNode root) {
if (root == null) return new ArrayList<>();
Stack s1 = new Stack<>();
Stack s2 = new Stack<>();
s1.push(root);
while (!s1.isEmpty()) {
TreeNode curr = s1.pop();
s2.push(curr);
if (curr.left != null) s1.push(curr.left);
if (curr.right != null) s1.push(curr.right);
}
List ans = new ArrayList<>();
while (!s2.isEmpty()) {
ans.add(s2.pop().val);
}
return ans;
}
vector postorderTraversal(TreeNode* root) {
if (!root) return {};
stack s1, s2;
s1.push(root);
while (!s1.empty()) {
TreeNode* curr = s1.top(); s1.pop();
s2.push(curr);
if (curr->left) s1.push(curr->left);
if (curr->right) s1.push(curr->right);
}
vector ans;
while (!s2.empty()) {
ans.push_back(s2.top()->val);
s2.pop();
}
return ans;
}
void postorderTraversal(struct TreeNode* root, int* result, int* returnSize) {
if (!root) return;
struct TreeNode* s1[1000];
struct TreeNode* s2[1000];
int top1 = -1, top2 = -1;
s1[++top1] = root;
while (top1 >= 0) {
struct TreeNode* curr = s1[top1--];
s2[++top2] = curr;
if (curr->left) s1[++top1] = curr->left;
if (curr->right) s1[++top1] = curr->right;
}
*returnSize = 0;
while (top2 >= 0) {
result[(*returnSize)++] = s2[top2--]->val;
}
}
public IList PostorderTraversal(TreeNode root) {
if (root == null) return new List();
Stack s1 = new Stack();
Stack s2 = new Stack();
s1.Push(root);
while (s1.Count > 0) {
TreeNode curr = s1.Pop();
s2.Push(curr);
if (curr.left != null) s1.Push(curr.left);
if (curr.right != null) s1.Push(curr.right);
}
List ans = new List();
while (s2.Count > 0) {
ans.Add(s2.Pop().val);
}
return ans;
}
