1+ /*
2+ Author: king, wangjingui@outlook.com
3+ Date: Dec 31, 2014
4+ Problem: Binary Search Tree Iterator
5+ Difficulty: Easy
6+ Source: https://oj.leetcode.com/problems/binary-search-tree-iterator/
7+ Notes:
8+ Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
9+
10+ Calling next() will return the next smallest number in the BST.
11+
12+ Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.
13+
14+ Solution: Inorder traversal.
15+ */
16+ /**
17+ * Definition for binary tree
18+ * public class TreeNode {
19+ * int val;
20+ * TreeNode left;
21+ * TreeNode right;
22+ * TreeNode(int x) { val = x; }
23+ * }
24+ */
25+
26+ public class BSTIterator {
27+
28+ public BSTIterator (TreeNode root ) {
29+ stk =new Stack <TreeNode >();
30+ node =root ;
31+ }
32+
33+ /** @return whether we have a next smallest number */
34+ public boolean hasNext () {
35+ if (stk .isEmpty () ==true &&node ==null )return false ;
36+ return true ;
37+ }
38+
39+ /** @return the next smallest number */
40+ public int next () {
41+ if (stk .isEmpty () ==true &&node ==null )return 0 ;
42+ while (node !=null ) {
43+ stk .push (node );
44+ node =node .left ;
45+ }
46+ int res =0 ;
47+ node =stk .pop ();
48+ res =node .val ;
49+ node =node .right ;
50+ return res ;
51+ }
52+ private Stack <TreeNode >stk ;
53+ private TreeNode node ;
54+ }
55+
56+ /**
57+ * Your BSTIterator will be called like this:
58+ * BSTIterator i = new BSTIterator(root);
59+ * while (i.hasNext()) v[f()] = i.next();
60+ */
