文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

實(shí)現(xiàn)二叉搜索樹（BST）的中序遍歷迭代器 BSTIterator 類：

• BSTIterator(TreeNode root) 初始化 BSTIterator 類的實(shí)例。
  二叉搜索樹的根節(jié)點(diǎn) root 作為構(gòu)造函數(shù)的參數(shù)傳入。
  內(nèi)部指針使用一個(gè)不存在于樹中且小于樹中任意值的數(shù)值來初始化。
• boolean hasNext() 如果當(dāng)前指針在中序遍歷序列中，存在右側(cè)數(shù)值，返回 true ，否則返回 false 。
• int next() 將指針在中序遍歷序列中向右移動(dòng)，然后返回移動(dòng)后指針?biāo)笖?shù)值。
• boolean hasPrev() 如果當(dāng)前指針在中序遍歷序列中，存在左側(cè)數(shù)值，返回 true ，否則返回 false 。
• int prev() 將指針在中序遍歷序列中向左移動(dòng)，然后返回移動(dòng)后指針?biāo)笖?shù)值。

注意，雖然我們使用樹中不存在的最小值來初始化內(nèi)部指針，第一次調(diào)用 next() 需要返回二叉搜索樹中最小的元素。

你可以假設(shè) next() 和 prev() 的調(diào)用總是有效的。
即，當(dāng) next()/prev() 被調(diào)用的時(shí)候，在中序遍歷序列中一定存在下一個(gè)/上一個(gè)元素。

進(jìn)階：你可以不提前遍歷樹中的值來解決問題嗎？

示例 1:

輸入 ["BSTIterator", "next", "next", "prev", "next", "hasNext", "next", "next", "next", "hasNext", "hasPrev", "prev", "prev"] [[[7, 3, 15, null, null, 9, 20]], [null], [null], [null], [null], [null], [null], [null], [null], [null], [null], [null], [null]] 輸出 [null, 3, 7, 3, 7, true, 9, 15, 20, false, true, 15, 9]解釋 // 劃線的元素表示指針當(dāng)前的位置。 BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]); // 當(dāng)前狀態(tài)為 <u> </u> [3, 7, 9, 15, 20] bSTIterator.next(); // 狀態(tài)變?yōu)?[<u>3</u>, 7, 9, 15, 20], 返回 3 bSTIterator.next(); // 狀態(tài)變?yōu)?[3, <u>7</u>, 9, 15, 20], 返回 7 bSTIterator.prev(); // 狀態(tài)變?yōu)?[<u>3</u>, 7, 9, 15, 20], 返回 3 bSTIterator.next(); // 狀態(tài)變?yōu)?[3, <u>7</u>, 9, 15, 20], 返回 7 bSTIterator.hasNext(); // 返回 true bSTIterator.next(); // 狀態(tài)變?yōu)?[3, 7, <u>9</u>, 15, 20], 返回 9 bSTIterator.next(); // 狀態(tài)變?yōu)?[3, 7, 9, <u>15</u>, 20], 返回 15 bSTIterator.next(); // 狀態(tài)變?yōu)?[3, 7, 9, 15, <u>20</u>], 返回 20 bSTIterator.hasNext(); // 返回 false bSTIterator.hasPrev(); // 返回 true bSTIterator.prev(); // 狀態(tài)變?yōu)?[3, 7, 9, <u>15</u>, 20], 返回 15 bSTIterator.prev(); // 狀態(tài)變?yōu)?[3, 7, <u>9</u>, 15, 20], 返回 9提示: 樹中節(jié)點(diǎn)個(gè)數(shù)的范圍是 [1, 10^5] 。 0 <= Node.val <= 106 最多調(diào)用 105 次 hasNext、 next、 hasPrev 和 prev 。

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

2. 解題

• 用棧來進(jìn)行中序遍歷
• 用數(shù)組來存儲(chǔ)已經(jīng)遍歷過的節(jié)點(diǎn)（被彈棧的），同時(shí)用一個(gè) idx 記錄當(dāng)前的位置，如果超出數(shù)組范圍就去棧內(nèi)取節(jié)點(diǎn)

/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/ class BSTIterator {stack<TreeNode*> nstack;vector<TreeNode*> pstack;int prevIdx = 0; public:BSTIterator(TreeNode* root) {while(root){nstack.push(root);root = root->left;}}bool hasNext() {return !nstack.empty() || prevIdx+1 < pstack.size();}int next() {if(prevIdx+1 < pstack.size())return pstack[++prevIdx]->val;TreeNode* node = nstack.top();nstack.pop();pstack.push_back(node);prevIdx = pstack.size()-1;int v = node->val;TreeNode* t = node->right;while(t){nstack.push(t);t = t->left;}return v;}bool hasPrev() {return prevIdx > 0;}int prev() {prevIdx--;return pstack[prevIdx]->val;} };/*** Your BSTIterator object will be instantiated and called as such:* BSTIterator* obj = new BSTIterator(root);* bool param_1 = obj->hasNext();* int param_2 = obj->next();* bool param_3 = obj->hasPrev();* int param_4 = obj->prev();*/

304 ms 147 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關(guān)注我的公眾號（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

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

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