Binary Search Tree Iterator解题报告

Description:

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.

题意:

给一个二叉搜索树的根节点，实现从小到大的迭代，每次调用函数next()都输出当前最小的节点的值，hasNext()则用于检测是否还有剩下没输出的节点。

Link:

https://leetcode.com/problems/binary-search-tree-iterator/description/

解题方法：

对于二叉搜索树，中序遍历是最直接的方法，但是这道题要求O(h) space，也就是说差不多每层只能储存1个节点。
所以在栈里面，从根节点开始，只压栈本身和左孩子。
当每次调用next()的时候，弹出一个结点，如果这个节点有右孩子，则把右孩子当成root再进行一次构造函数。

Time Complexity：

构造函数O(h) time O(h) space
hasNext() O(1) time
next() O(1) time

完整代码：

class BSTIterator 
{
public:
    BSTIterator(TreeNode *root) 
    {
        while(root)
        {
            S.push(root);
            root = root->left;
        }
    }
    
    /** @return whether we have a next smallest number */
    bool hasNext() 
    {
        return !S.empty();
    }

    /** @return the next smallest number */
    int next() 
    {
        TreeNode* curr = S.top();
        S.pop();
        if(curr->right)
        {
            TreeNode* rightChild = curr->right; 
            while(rightChild)
            {
                S.push(rightChild);
                rightChild = rightChild->left;
            }
        }
        return curr->val;
    }
private:
    stack<TreeNode*> S;
};