import java.util.Stack;
class PostorderIterator {
private Stack<Node> stack = new Stack<>();
private Node prevProcessed = null;
public PostorderIterator(Node root) {
pushLeftSubtree(root);
}
private void pushLeftSubtree(Node node) {
while (node != null) {
stack.push(node);
node = node.left;
}
}
public int next() {
if (!hasNext()) {
return -1;
}
while (!stack.isEmpty()) {
Node curr = stack.peek();
// If there's no right child OR right child has already been processed
if (curr.right == null || curr.right == prevProcessed) {
stack.pop();
prevProcessed = curr;
return curr.val; // Corrected return statement
}
// Process right subtree
pushLeftSubtree(curr.right);
}
return -1; // Should never reach here if hasNext() is checked before calling next()
}
public boolean hasNext() {
return !stack.isEmpty();
}
}
class Node {
int val;
Node left, right;
public Node(int val) {
this.val = val;
this.left = null;
this.right = null;
}
}
Comments
0 B
|0 👍
/0 👎
0 B
|👍
/👎