C++刷leetcode（173. 二叉搜索树迭代器）【中序遍历】

糖逗

题目描述：

1. 实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。
   
2. 
   
3. 调用 next() 将返回二叉搜索树中的下一个最小的数。
   
4. 
   
5.  
   
6. 
   
7. 示例：
   
8. 
   
9. 
   
10. 
    
11. BSTIterator iterator = new BSTIterator(root);
    
12. iterator.next();    // 返回 3
    
13. iterator.next();    // 返回 7
    
14. iterator.hasNext(); // 返回 true
    
15. iterator.next();    // 返回 9
    
16. iterator.hasNext(); // 返回 true
    
17. iterator.next();    // 返回 15
    
18. iterator.hasNext(); // 返回 true
    
19. iterator.next();    // 返回 20
    
20. iterator.hasNext(); // 返回 false
    
21.  
    
22. 
    
23. 提示：
    
24. 
    
25. next() 和 hasNext() 操作的时间复杂度是 O(1)，并使用 O(h) 内存，其中 h 是树的高度。
    
26. 你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 中至少存在一个下一个最小的数。
    
27. 
    
28. 来源：力扣（LeetCode）
    
29. 链接：https://leetcode-cn.com/problems/binary-search-tree-iterator
    
30. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class BSTIterator {
   
2. private:
   
3.     queue<int> temp;
   
4.     void middle(TreeNode*cur){
   
5.         if(cur == NULL) return;
   
6.         middle(cur -> left);
   
7.         temp.push(cur -> val);
   
8.         middle(cur -> right);
   
9.     }
   
10. public:
    
11.     BSTIterator(TreeNode* root) {
    
12.         middle(root);
    
13. 
    
14.     }
    
15.     /** @return the next smallest number */
    
16.     int next() {
    
17.         int res = temp.front();
    
18.         temp.pop();
    
19.         return res;
    
20.    
    
21.     }
    
22.    
    
23.     /** @return whether we have a next smallest number */
    
24.     bool hasNext() {
    
25.         if(temp.empty()) return false;
    
26.         return true;
    
27.     }
    
28. };

复制代码