import sun.reflect.generics.tree.Tree;

import java.util.Stack;
import java.util.regex.Pattern;

/**
 * Created by liuxz on 17-4-13.
 */
public class Leet173BinarySearchTreeIterator {
    private TreeNode current;
    private Stack<TreeNode> stack;

//    public void BSTIterator(TreeNode root) {
//        current = root;
//        stack = new Stack<TreeNode>();
//    }
//
//    /** @return whether we have a next smallest number */
//    public boolean hasNext() {
//        return !stack.isEmpty() || current!=null;
//    }
//
//    /** @return the next smallest number */
//    public int next() {
//        while (!stack.isEmpty() || current!=null) {
//            if (current!=null) {
//                stack.push(current);
//                current = current.left;
//            } else {
//                current = stack.peek().right;
//                break;
//            }
//        }
//        TreeNode node = stack.pop();
//        return node.val;
//    }
//
//    public static void main(String[] args){
//        Leet173BinarySearchTreeIterator xx = new Leet173BinarySearchTreeIterator();
//        TreeNode root = new TreeNode(0);
//        root.left = new TreeNode(1);
//        root.left.left = new TreeNode(2);
//        root.left.right = new TreeNode(5);
//        root.left.right.left = new TreeNode(6);
//        root.right = new TreeNode(3);
//        root.right.right = new TreeNode(4);
//        xx.BSTIterator(root);
//        while(xx.hasNext()){
//            System.out.println(xx.next());
//        }
//    }
}

@@ -33,16 +33,45 @@
 .Tree;%0A%0A
+import java.util.LinkedList;%0A
 import j
@@ -222,43 +222,18 @@
 ate 
-TreeNode current;%0A    private Stack
+LinkedList
 %3CTre
@@ -247,18 +247,16 @@
 stack;%0A%0A
-//
     publ
@@ -262,16 +262,31 @@
 lic 
-void BST
+Leet173BinarySearchTree
 Iter
@@ -307,26 +307,24 @@
 root) %7B%0A
-//
         
 current 
@@ -319,78 +319,151 @@
     
-current = root;%0A//        stack = new Stack%3CTreeNode%3E();%0A//
+stack = new LinkedList%3C%3E();%0A        for (TreeNode temp = root; temp != null; temp = temp.left)%7B%0A            stack.push(temp);%0A        %7D%0A
     %7D%0A
-//%0A//
+%0A
     
@@ -508,34 +508,32 @@
 llest number */%0A
-//
     public boole
@@ -539,34 +539,32 @@
 ean hasNext() %7B%0A
-//
         return !
@@ -566,56 +566,31 @@
 urn 
-!
 stack.
-isEmpty() %7C%7C current!=null;%0A//
+size()%3E0;%0A
     %7D%0A
-//%0A//
+%0A
     
@@ -629,18 +629,16 @@
 mber */%0A
-//
     publ
@@ -653,26 +653,24 @@
 ext() %7B%0A
-//
         
 while (!
@@ -665,136 +665,47 @@
     
-while (!stack.isEmpty() %7C%7C current!=null) %7B%0A//            if (current!=null) %7B%0A//                stack.push(current
+TreeNode result = stack.pop(
 );%0A
-//
         
     
@@ -704,205 +704,116 @@
     
-        current = current.left;%0A//            %7D else %7B%0A//                current = stack.peek().right;%0A//                break;%0A//            %7D%0A//        %7D%0A//        TreeNode node = stack.pop();%0A//
+for (TreeNode temp = result.right; temp!= null ; temp = temp.left)%7B%0A            stack.push(temp);%0A        %7D%0A
     
@@ -827,31 +827,28 @@
 urn 
-node
+result
 .val;%0A
-//
     %7D%0A
-//%0A//
+%0A%0A
     
@@ -887,26 +887,25 @@
  args)%7B%0A
-//
+%0A
         
 Leet173B
@@ -900,94 +900,49 @@
     
-Leet173BinarySearchTreeIterator xx = new Leet173BinarySearchTreeIterator(
+TreeNode root = new TreeNode(8
 );%0A
-//
         
 Tree
@@ -933,36 +933,74 @@
 8);%0A        
-TreeNode roo
+root.left = new TreeNode(3);%0A        root.left.lef
 t = new Tree
@@ -1008,14 +1008,12 @@
 ode(
-0
+1
 );%0A
-//
     
@@ -1017,32 +1017,38 @@
        root.left
+.right
  = new TreeNode(
@@ -1051,14 +1051,12 @@
 ode(
-1
+6
 );%0A
-//
     
@@ -1061,32 +1061,38 @@
       root.left.
+right.
 left = new TreeN
@@ -1099,14 +1099,12 @@
 ode(
-2
+4
 );%0A
-//
     
@@ -1114,33 +1114,38 @@
  root.left.right
+.right
- 
 = new TreeNode(5
@@ -1147,14 +1147,12 @@
 ode(
-5
+7
 );%0A
-//
     
@@ -1156,38 +1156,28 @@
        root.
-left.right.lef
+righ
 t = new Tree
@@ -1185,14 +1185,13 @@
 ode(
-6
+10
 );%0A
-//
     
@@ -1196,32 +1196,38 @@
       root.right
+.right
  = new TreeNode(
@@ -1230,14 +1230,13 @@
 ode(
-3
+14
 );%0A
-//
     
@@ -1247,32 +1247,37 @@
 root.right.right
+.left
  = new TreeNode(
@@ -1276,17 +1276,18 @@
 reeNode(
-4
+13
 );%0A//   
@@ -1313,18 +1313,104 @@
 (root);%0A
-//
+        Leet173BinarySearchTreeIterator xx = new Leet173BinarySearchTreeIterator(root);%0A
         
@@ -1430,18 +1430,16 @@
 ext())%7B%0A
-//
         
@@ -1473,18 +1473,16 @@
 ext());%0A
-//
         
@@ -1483,18 +1483,16 @@
       %7D%0A
-//
     %7D%0A%7D%0A

complete 173