LeetCode173—Binary Search Tree Iterator

骑猪看日落 2022-07-14 06:26 151阅读 0赞

## 原题 ##

[原题链接][Link 1]

> 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.

## 分析 ##

设计一个二叉查找树 BST 的迭代器，其中`next()`方法可以始终返回其最小值，而`hasNext()`判定是否还有下一个节点的值可供返回，也即是否遍历完了整棵树。

BST的特性就是中序遍历是升序的，因此，我在构造函数中，对BST首先中序遍历，并将结果保存在类中成员`vector<int>values_`中。

除此之外，类中还有两个变量，一个表示当前遍历到什么位置，一个表示BST的节点个数，也就是vector的size。那么只要当前的位置小于size，则说明BST还没有遍历完，则`hasNext`返回true。

class BSTIterator {
    
    private:
        vector<int>values_;
        int currIndex_;
        int size_;
    
        void InorderTraverse(TreeNode * root)
        {
            if(NULL==root)
                return;
            InorderTraverse(root->left);
            values_.push_back(root->val);
            InorderTraverse(root->right);
        }
    public:
        BSTIterator(TreeNode *root):currIndex_(0)
        {
            InorderTraverse(root);
            size_=values_.size();
        }
    
        /** @return whether we have a next smallest number */
        bool hasNext() {
            return currIndex_<size_;
        }
    
        /** @return the next smallest number */
        int next() {
            return values_[currIndex_++];
        }
    };

不过后来想了想，不从题目本身考虑，只从设计来说，应该有一些小缺陷，比如当遍历完成后应该初始化一下，否则当`hasNext`返回false时，迭代器就失效了。

[Link 1]: https://leetcode.com/problems/binary-search-tree-iterator/