Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * Definition for a binary tree node.
- * public class TreeNode {
- * int val;
- * TreeNode left;
- * TreeNode right;
- * TreeNode(int x) { val = x; }
- * }
- */
- class BSTIterator {
- LinkedList<Step> steps;
- public BSTIterator(TreeNode root) {
- steps = new LinkedList<Step>();
- steps.add(new Step(root));
- }
- /** @return the next smallest number */
- public int next() {
- System.out.println("calling next");
- move();
- int result = steps.getFirst().node.val;
- System.out.println("next returned " + result);
- return result;
- }
- private void move() {
- System.out.println("calling move");
- if (steps.isEmpty()) return;
- for (;;) {
- Step step = steps.getFirst();
- if (step.visitedLeft == false) {
- System.out.println("left from " + step.node.val);
- step.visitedLeft = true;
- if (step.node.left != null) {
- steps.addFirst(new Step(step.node.left));
- continue;
- }
- }
- if (!step.returned) {
- System.out.println("return " + step.node.val);
- step.returned = true;
- break;
- }
- if (step.visitedRight == false) {
- System.out.println("right from " + step.node.val);
- step.visitedRight = true;
- if (step.node.right != null) {
- steps.addFirst(new Step(step.node.right));
- continue;
- }
- }
- System.out.println("go up");
- steps.removeFirst();
- }
- }
- /** @return whether we have a next smallest number */
- public boolean hasNext() {
- System.out.println("calling hasNext");
- for (int i = 0; i < steps.size(); i++) {
- Step step = steps.get(i);
- if (!step.visitedLeft || !step.visitedRight || !step.returned) {
- System.out.println("hasNext: true");
- return true;
- }
- }
- System.out.println("hasNext: false");
- return false;
- }
- class Step {
- TreeNode node;
- boolean visitedLeft;
- boolean visitedRight;
- boolean returned;
- public Step(TreeNode node ) {
- this.node = node;
- }
- }
- }
- /**
- * Your BSTIterator object will be instantiated and called as such:
- * BSTIterator obj = new BSTIterator(root);
- * int param_1 = obj.next();
- * boolean param_2 = obj.hasNext();
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement