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
- Initialize an empty array
ansto store the result. - Define a helper function
traversal(curr):- If the current node is
null, return. - Recursively traverse the left subtree.
- Recursively traverse the right subtree.
- Push the current node’s value into ans.
- If the current node is
- Call
traversal(root)to start the traversal from the root. - Return the result array ans.
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:
ans = []
Start traversal(root = 1)
→ curr = 1
→ traversal(curr.left = 2)
→ curr = 2
→ traversal(curr.left = null) → return
→ ans.push(2) → ans = [2]
→ traversal(curr.right = 4)
→ curr = 4
→ traversal(curr.left = null) → return
→ ans.push(4) → ans = [2, 4]
→ traversal(curr.right = null) → return
← return to curr = 2 → done
← return to curr = 1
→ ans.push(1) → ans = [2, 4, 1]
→ traversal(curr.right = 3)
→ curr = 3
→ traversal(curr.left = null) → return
→ ans.push(3) → ans = [2, 4, 1, 3]
→ traversal(curr.right = null) → return
← return to curr = 1 → done
Traversal complete.
Final ans = [2, 4, 1, 3]
Output: Result: [2, 4, 1, 3]
var postorderTraversal = function(root) {
let ans = [];
function traversal(curr){
if(!curr) return;
traversal(curr.left);
traversal(curr.right);
ans.push(curr.val);
}
traversal(root);
return ans;
}
def postorderTraversal(root):
ans = []
def traversal(curr):
if not curr:
return
traversal(curr.left)
traversal(curr.right)
ans.append(curr.val)
traversal(root)
return ans
public List postorderTraversal(TreeNode root) {
List ans = new ArrayList<>();
void traversal(TreeNode curr) {
if (curr == null) return;
traversal(curr.left);
traversal(curr.right);
ans.add(curr.val);
}
traversal(root);
return ans;
}
vector postorderTraversal(TreeNode* root) {
vector ans;
function traversal = [&](TreeNode* curr) {
if (!curr) return;
traversal(curr->left);
traversal(curr->right);
ans.push_back(curr->val);
};
traversal(root);
return ans;
}
void traversal(struct TreeNode* curr, int* ans, int* returnSize) {
if (!curr) return;
traversal(curr->left, ans, returnSize);
traversal(curr->right, ans, returnSize);
ans[(*returnSize)++] = curr->val;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize) {
int* ans = malloc(100 * sizeof(int)); // Assumes max 100 nodes
*returnSize = 0;
traversal(root, ans, returnSize);
return ans;
}
public IList PostorderTraversal(TreeNode root) {
List ans = new List();
void Traversal(TreeNode curr) {
if (curr == null) return;
Traversal(curr.left);
Traversal(curr.right);
ans.Add(curr.val);
}
Traversal(root);
return ans;
}
