@@ -0,0 +1,2010 @@
+/***%0A * Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.%0A *%0A * Calling next() will return the next smallest number in the BST.%0A *%0A * Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.%0A *%0A * Consider the following tree:%0A *       4%0A *     /   %5C%0A *    3     6%0A *   / %5C   / %5C%0A *  1   2 5   7%0A */%0A/**%0A * Definition for binary tree%0A * public class TreeNode %7B%0A *     int val;%0A *     TreeNode left;%0A *     TreeNode right;%0A *     TreeNode(int x) %7B val = x; %7D%0A * %7D%0A */%0Aimport java.util.Stack;%0Apublic class BinarySearchTreeIterator %7B%0A    private Stack%3CTreeNode%3E stk = new Stack%3CTreeNode%3E();%0A    public BinarySearchTreeIterator(TreeNode root) %7B%0A        for (; root != null; stk.push(root), root = root.left);%0A    %7D%0A%0A    /** @return whether we have a next smallest number */%0A    public boolean hasNext() %7B%0A        return !stk.isEmpty();%0A    %7D%0A%0A    /** @return the next smallest number */%0A    public int next() %7B%0A        TreeNode tempNode = stk.pop();%0A        for(TreeNode node = tempNode.right; node != null; stk.push(node), node = node.left);%0A        return tempNode.val;%0A    %7D%0A%0A    public static void main(String args%5B%5D) %7B%0A        TreeNode n1 = new TreeNode(1);%0A        TreeNode n2 = new TreeNode(2);%0A        TreeNode n3 = new TreeNode(3);%0A        TreeNode n4 = new TreeNode(4);%0A        TreeNode n5 = new TreeNode(5);%0A        TreeNode n6 = new TreeNode(6);%0A        TreeNode n7 = new TreeNode(7);%0A        n4.left = n3; n4.right = n6;%0A        n3.left = n1; n3.right = n2;%0A        n6.left = n5; n6.right = n7;%0A        BinarySearchTreeIterator i = new BinarySearchTreeIterator(n4);%0A        int nl%5B%5D = new int%5B7%5D;%0A        int k = 0;%0A        while(i.hasNext()) nl%5Bk++%5D = i.next();%0A        for (int n: nl)%0A            System.out.printf(%22%25d%5Cn%22, n);%0A    %7D%0A%7D%0A/**%0A * Your BSTIterator will be called like this:%0A * BSTIterator i = new BSTIterator(root);%0A * while (i.hasNext()) v%5Bf()%5D = i.next();%0A */%0A

add BinarySearchTreeIterator.java