[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.
Callingnext()will return the next smallest number in the BST.
Note:next()andhasNext()should run in average O(1) time and uses O(h) memory, wherehis the height of the tree.
Credits:
Special thanks to@tsfor adding this problem and creating all test cases.
这道题主要就是考二叉树的中序遍历的非递归形式，需要额外定义一个栈来辅助，二叉搜索树的建树规则就是左<根<右，用中序遍历即可从小到大取出所有节点。代码如下：
?| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
/**
* 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) {
while (root) {
s.push(root);
root = root->left;
}
}
/** @return whether we have a next smallest number */
bool hasNext() {
return !s.empty();
}
/** @return the next smallest number */
int next() {
TreeNode *n = s.top();
s.pop();
int res = n->val;
if (n->right) {
n = n->right;
while (n) {
s.push(n);
n = n->left;
}
}
return res;
}
private:
stack<TreeNode*> s;
};
/**
* Your BSTIterator will be called like this:
* BSTIterator i = BSTIterator(root);
* while (i.hasNext()) cout << i.next();
*/
|
原文链接：https://www.cnblogs.com/grandyang/p/4231455.html
如果您对该产品感兴趣，请填写办理（客服微信：xiaoxiongyidong）
发表评论
◎欢迎参与讨论，请在这里发表您的看法、交流您的观点。