LeetCode: 173. Binary Search Tree Iterator
LeetCode: 173. Binary Search Tree Iterator
题目描述
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.
解题思路
构建中序遍历的线索二叉树(利用哈希表(unordered_map
)来存储线索), 线索的顺序就是迭代器遍历的顺序。
AC 代码
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
class BSTIterator {
public:
BSTIterator(TreeNode *root) {
TreeNode* pre = nullptr;
makeTreeNextMap(root, pre);
tree2Next[pre] = nullptr;
curNode = tree2Next[nullptr];
}
/** @return whether we have a next smallest number */
bool hasNext() {
return !(curNode == nullptr);
}
/** @return the next smallest number */
int next() {
int cur = curNode->val;
curNode = tree2Next[curNode];
return cur;
}
private:
void makeTreeNextMap(TreeNode* root, TreeNode*& pre)
{
if(root == nullptr) return ;
makeTreeNextMap(root->left, pre);
tree2Next[pre] = root;
pre=root;
makeTreeNextMap(root->right, pre);
}
private:
unordered_map<TreeNode*, TreeNode*> tree2Next;
TreeNode* curNode;
};
/** * Your BSTIterator will be called like this: * BSTIterator i = BSTIterator(root); * while (i.hasNext()) cout << i.next(); */