LeetCode 144: Binary Tree Preorder Traversal
LeetCode 144 Solution Explanation
Explanation
To perform a preorder traversal of a binary tree iteratively, we can use a stack to simulate the recursive call stack. The preorder traversal visits the root node first, then recursively visits the left subtree, and finally recursively visits the right subtree.
Here's the step-by-step algorithm:
- Initialize an empty stack and a list to store the result.
- Push the root node onto the stack.
- While the stack is not empty, pop a node from the stack.
- Add the node's value to the result list.
- If the node has a right child, push the right child onto the stack.
- If the node has a left child, push the left child onto the stack.
- Repeat steps 3-6 until the stack is empty.
Time complexity: O(n) - where n is the number of nodes in the tree. Space complexity: O(n) - in the worst-case scenario where the binary tree is skewed, the stack can hold all the nodes.
LeetCode 144 Solutions in Java, C++, Python
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
result.add(node.val);
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
return result;
}Interactive Code Editor for LeetCode 144
Improve Your LeetCode 144 Solution
Use the editor below to refine the provided solution for LeetCode 144. 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...