LeetCode 1586: Binary Search Tree Iterator II
LeetCode 1586 Solution Explanation
Explanation:
To implement the Binary Search Tree Iterator II, we can use the same approach as the Binary Search Tree Iterator but with the additional functionalities of hasPrev() and prev() methods.
- Create a stack to store the nodes in the path from the root to the current node.
- In the constructor, initialize the stack with nodes up to the leftmost node.
- The
hasNext()method returns true if there are more nodes to visit (i.e., the stack is not empty). - The
next()method returns the next smallest node and updates the stack accordingly. - The
hasPrev()method returns true if there are previous nodes to visit (i.e., the stack is not empty). - The
prev()method returns the previous largest node and updates the stack accordingly.
:
LeetCode 1586 Solutions in Java, C++, Python
class BSTIterator {
Stack<TreeNode> stack;
public BSTIterator(TreeNode root) {
stack = new Stack<>();
while (root != null) {
stack.push(root);
root = root.left;
}
}
public boolean hasNext() {
return !stack.isEmpty();
}
public int next() {
TreeNode node = stack.pop();
int result = node.val;
node = node.right;
while (node != null) {
stack.push(node);
node = node.left;
}
return result;
}
public boolean hasPrev() {
return !stack.isEmpty();
}
public int prev() {
TreeNode node = stack.pop();
int result = node.val;
node = node.left;
while (node != null) {
stack.push(node);
node = node.right;
}
return result;
}
}Interactive Code Editor for LeetCode 1586
Improve Your LeetCode 1586 Solution
Use the editor below to refine the provided solution for LeetCode 1586. 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...