文章目錄

• • 1. 題目信息
  • 2. 二叉樹中序遍歷

1. 題目信息

實現(xiàn)一個二叉搜索樹迭代器。你將使用二叉搜索樹的根節(jié)點初始化迭代器。

調(diào)用 next() 將返回二叉搜索樹中的下一個最小的數(shù)。

示例：

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

提示：

next() 和 hasNext() 操作的時間復(fù)雜度是 O(1)，并使用 O(h) 內(nèi)存，其中 h 是樹的高度。
你可以假設(shè) next() 調(diào)用總是有效的，也就是說，當調(diào)用 next() 時，BST 中至少存在一個下一個最小的數(shù)。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/binary-search-tree-iterator
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 二叉樹中序遍歷

• 搜索樹中序是非降的
  

class BSTIterator {stack<TreeNode*> stk;TreeNode *cur; public:BSTIterator(TreeNode* root) {cur = root;}/** @return the next smallest number */int next() {if(!hasNext())return -1;while(cur){stk.push(cur);cur = cur->left;}cur = stk.top();int v = cur->val;stk.pop();cur = cur->right;return v;}/** @return whether we have a next smallest number */bool hasNext() {return !stk.empty() || cur;} };/*** 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();*/

總結(jié)

以上是生活随笔為你收集整理的LeetCode 173. 二叉搜索树迭代器（中序遍历）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。