阅读量:0
leetcode173. 二叉搜索树迭代器
实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器：
BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。
boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。
**int next()**将指针向右移动，然后返回指针处的数字。
注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。
你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 的中序遍历中至少存在一个下一个数字。
示例：
输入
[“BSTIterator”, “next”, “next”, “hasNext”, “next”, “hasNext”, “next”, “hasNext”, “next”, “hasNext”]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
输出
[null, 3, 7, true, 9, true, 15, true, 20, false]
解释
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9,20]);
bSTIterator.next(); // 返回 3 bSTIterator.next(); // 返回 7
bSTIterator.hasNext(); // 返回 True bSTIterator.next(); // 返回 9
bSTIterator.hasNext(); // 返回 True bSTIterator.next(); // 返回 15
bSTIterator.hasNext(); // 返回 True bSTIterator.next(); // 返回 20
bSTIterator.hasNext(); // 返回 False
算法思想
看起来题意比较难理解，实际上使用二叉搜索树的性质，由于二叉搜索树的中序遍历是递增序列。我们生成一个二叉树的中序遍历序列即可，
具体题目是
| leetcode98 | 验证二叉搜索树 |
|---|
我写过完整题解。
我们可以创建一个迭代器，通过预先计算树的中序遍历结果，然后按顺序返回这些值。
算法步骤
1.在构造函数中，使用辅助函数 inorderTraversal 对二叉搜索树进行中序遍历，并将结果存储在 arr 数组中。
2.维护一个索引 idx 来记录当前遍历到的位置。
3.next 函数返回当前索引所指向的元素，并递增索引。
4.hasNext 函数检查索引是否小于数组长度，以确定是否还有更多的元素可以遍历。
但如果你觉得这道题就这样轻松解决了，那么你就错了，其实还有很多细节要注意！！
具体代码
如果你仔细看题意，会发现leetcode的官方题解是有一点问题的，题目的描述是
int next()将指针向右移动，然后返回指针处的数字。
那么我们实现next函数时候应该先移动指针，再返回数字，所以应该是前缀++，而不是题解中给出的后缀++，相应的初始化时候数组索引idx应该为-1，即满足题意中
注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。
之后hasNext函数也要相应更改，注意
这里有一个大坑
如果直接使用
if((idx < (arr.size()-1)) ) return true; else return false; 是过不了的，不信你试试，必须将arr.size()将转为int类型。
vector中size()的坑
在使用C++的vector时，需要注意size()函数返回的是unsigned int类型，其取值范围为0到2^32 - 1。当vector为空时，即size()返回值为0，此时对结果进行减1操作会导致溢出，得到的结果并不是-1，而是一个很大的数。
为了避免这种情况，可以采取以下两种策略来处理size()的返回值：
1.将vector.size()强制转换为int类型
2.使用一个int变量去接收vector.size()的值
这只是其一，该题无法通过的原因并不是这一点。
无符号整数类型和其他类型的加减
if((idx < (arr.size()-1)) ) return true; else return false; 这段代码真正有问题的原因是当无符号整数unsigned int类型和int类型进行加减或者比大小时，int类型会被强转为无符号整数类型！！如下图所示：
可以看到int类型-1和unsigned int类型的0相加，结果为-1转换为无符号类型的结果即2的32次方-1.
无符号类型的加减规则如下
所以本体的具体代码如下：
class BSTIterator { private: void inorder(TreeNode* root, vector<int>& res) { if (!root) { return; } inorder(root->left, res); res.push_back(root->val); inorder(root->right, res); } vector<int> inorderTraversal(TreeNode* root) { vector<int> res; inorder(root, res); return res; } vector<int> arr; int idx; public: BSTIterator(TreeNode* root) { idx=-1; arr=inorderTraversal(root); } int next() { return arr[++idx]; } bool hasNext() { if((idx < ((int)arr.size()-1)) ) return true; else return false; } }; /** * 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(); */ 