LeetCode 145: Binary Tree Postorder Traversal
LeetCode 145 Solution Explanation
Explanation
To perform postorder traversal iteratively, we can use a stack to simulate the call stack of recursive function calls. The key idea is to visit the left subtree first, then the right subtree, and finally the root. We need two stacks: one for storing nodes to be processed, and another for storing the final result in reverse order.
- Start with an empty stack and push the root node onto it.
- While the stack is not empty:
- Pop a node from the stack.
- Add the node's value to the result stack.
- Push the node's left child (if exists) onto the processing stack.
- Push the node's right child (if exists) onto the processing stack.
- Once the processing stack is empty, all nodes have been visited, and we can pop values from the result stack to get the postorder traversal.
Time Complexity: O(n) - we visit each node once
Space Complexity: O(n) - in the worst case (skewed tree), the stack can hold all nodes
LeetCode 145 Solutions in Java, C++, Python
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
Stack<TreeNode> stack = new Stack<>();
Stack<Integer> postOrder = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode curr = stack.pop();
postOrder.push(curr.val);
if (curr.left != null) {
stack.push(curr.left);
}
if (curr.right != null) {
stack.push(curr.right);
}
}
while (!postOrder.isEmpty()) {
result.add(postOrder.pop());
}
return result;
}Interactive Code Editor for LeetCode 145
Improve Your LeetCode 145 Solution
Use the editor below to refine the provided solution for LeetCode 145. Select a programming language and try the following:
- Add import statements if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.
Loading editor...