实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。 调用 next() 将返回二叉搜索树中的下一个最小的数。
BSTIterator iterator = new BSTIterator(root); iterator.next(); // 返回 3 iterator.next(); // 返回 7 iterator.hasNext(); // 返回 true iterator.next(); // 返回 9 iterator.hasNext(); // 返回 true iterator.next(); // 返回 15 iterator.hasNext(); // 返回 true iterator.next(); // 返回 20 iterator.hasNext(); // 返回 false
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class BSTIterator { private: stack<int> m_s; public: BSTIterator(TreeNode* root) { stack<TreeNode *> s; TreeNode * pCurNode = root; while(!s.empty()||pCurNode) { if(pCurNode) { s.push(pCurNode); pCurNode = pCurNode->right; } else { TreeNode * pNode = s.top(); s.pop(); m_s.push(pNode->val); pCurNode = pNode->left; } } } /** @return the next smallest number */ int next() { int nVal = m_s.top(); m_s.pop(); return nVal; } /** @return whether we have a next smallest number */ bool hasNext() { if(m_s.empty()) return false; return true; } }; /** * 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(); */