本文主要是介绍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.
分析:
中序遍历即可。
代码:
/*** Definition for binary tree* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class BSTIterator {
public:stack<TreeNode*> tree;BSTIterator(TreeNode *root) {while(root){tree.push(root);root=root->left;}}/** @return whether we have a next smallest number */bool hasNext() {return !tree.empty();}/** @return the next smallest number */int next() {TreeNode* tmp=tree.top();tree.pop();TreeNode* right=tmp->right;while(right){tree.push(right);right=right->left;}return tmp->val;}
};/*** Your BSTIterator will be called like this:* BSTIterator i = BSTIterator(root);* while (i.hasNext()) cout << i.next();*/
这篇关于LeetCode *** 173. Binary Search Tree Iterator的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!