1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 //中序遍历的拆分
11 class BSTIterator 
12 {
13     stack<TreeNode*> s;
14     TreeNode* head;
15 public:
16     BSTIterator(TreeNode* root) 
17     {
18         head = root;
19         while(head != NULL)
20         {
21             s.push(head);
22             head = head->left;
23         }
24     }
25     
26     /** @return the next smallest number */
27     int next() 
28     {
29         TreeNode* p = s.top();
30         s.pop();
31         int temp = p->val;
32         p = p->right;
33         while(p)
34         {
35             s.push(p);
36             p = p->left;
37         }
38         return temp;
39     }
40     
41     /** @return whether we have a next smallest number */
42     bool hasNext() 
43     {
44         return !s.empty();
45     }
46 };
47 
48 /**
49  * Your BSTIterator object will be instantiated and called as such:
50  * BSTIterator* obj = new BSTIterator(root);
51  * int param_1 = obj->next();
52  * bool param_2 = obj->hasNext();
53  */