## [Leetcode]173. Binary Search Tree Iterator(C++)

### 题目描述

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling `next()` will return the next smallest number in the BST.

### Note

• `next()` and `hasNext()` should run in average O(1) time and uses O(h) memory, where h is the height of the tree.
• You may assume that `next()` call will always be valid, that is, there will be at least a next smallest number in the BST when `next()` is called.

### 解题思路

``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
#include <queue>

class BSTIterator {
public:
BSTIterator(TreeNode* root) { dfs(root); }

/** @return the next smallest number */
int next() {
int val = node_list.front();
node_list.pop();
return val;
}

/** @return whether we have a next smallest number */
bool hasNext() { return !node_list.empty(); }

private:
std::queue<int> node_list;

private:
void dfs(TreeNode* node) {
if (node == nullptr) return;
dfs(node->left);
node_list.push(node->val);
dfs(node->right);
}
};

/**
* Your BSTIterator object will be instantiated and called as such:
* BSTIterator* obj = new BSTIterator(root);
* int param_1 = obj->next();
* bool param_2 = obj->hasNext();
*/
``````
• 时间复杂度: O(n) for constructor, O(1) for the other twos operations
• 空间复杂度: O(n) for constructor, O(1) for the other twos operations

GitHub 代码同步地址： 173.BinarySearchTreeIterator.cpp

Built with Hugo
Theme Stack designed by Jimmy