[LeetCode]173. Binary Search Tree Iterator

Problem

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.

Example:

BSTIterator iterator = new BSTIterator(root);
iterator.next();    // return 3
iterator.next();    // return 7
iterator.hasNext(); // return true
iterator.next();    // return 9
iterator.hasNext(); // return true
iterator.next();    // return 15
iterator.hasNext(); // return true
iterator.next();    // return 20
iterator.hasNext(); // return false

Note:

• next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.
• You may assume that next() call will always be valid, that is, there will be at least a next smallest number in the BST when next() is called.

Solution

解析

题目给定一颗bst二分查找树，要求实现一个迭代器。用bst的根节点对迭代器初始化。同时要求迭代器实现两个接口，一个next()，返回BST中下一个最小的数；hasNext()确定是否还存在下一个节点。

从例子可以看出，解决这个问题，本质上还是要确定一个有序序列，我们可以通过中序遍历得到这个有序序列，同时设定一个指针，每次调用next()接口时，我们可以直接返回当前的最小数，调用完成，对指针进行更新，指向下一个位置；hasNext()可以通过判断指针的有效性来实现。

但是，这种解法，不符合要求。题目空间复杂度要求，时间复杂度要求一致；题目要求空间复杂度为O(h),h是树的高度；这里的空间复杂度为O(n),n是树的节点数。不过，也可以通过测试。

另一种解法，不事先把中序遍历序列得到。可以先存储一部分，然后在计算得到。无论哪种方法，一定和二叉树的中序遍历有关。这里使用二叉树的非递归形式进行遍历。先把从根节点的开始，把从最左边的路径进行遍历，之后在计算，当调用next()时，先pop出栈，同时要判断当前节点的右孩子是否存在，如果存在，再对子树的左分支进行入栈。hasNext()函数通过判断栈是否为空实现。

Code

O(N)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class BSTIterator {
public:
    BSTIterator(TreeNode* root) {//构造函数，完成指针和有序序列的初始化
        idx = 0;
        // 中序遍历的非递归形式
        TreeNode* todo = root;
        stack<TreeNode*> ss;
        data.clear();
        
        while (todo || !ss.empty()){
            if (todo){
                ss.push(todo);
                todo = todo->left;
            }else{
                todo = ss.top(); ss.pop();
                data.push_back(todo->val);
                todo = todo->right;
            }
        }
        
    }
    
    /** @return the next smallest number */
    int next() {
        return data[idx++];
    }
    
    /** @return whether we have a next smallest number */
    bool hasNext() {
        return idx < data.size();
    }
private:
    vector<int> data;//中序遍历得到的有序序列
    int idx;//指针
};

/**
 * 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();
 */

O(h)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class BSTIterator {
public:
    BSTIterator(TreeNode* root) {//构造函数完成对最初栈的初始化
        while (root){
            data.push(root);
            root = root->left;
        }
    }
    
    /** @return the next smallest number */
    int next() {
        TreeNode* node = data.top(); data.pop();
        int res = node->val;
        
        if (node->right){
            node = node->right;//对右分支对应的子树以及子树的左分支，进行入栈处理
            while (node){
                data.push(node);
                node = node->left;
            }
        }
        return res;
    }
    
    /** @return whether we have a next smallest number */
    bool hasNext() {
        return !data.empty();
    }
private:
    stack<TreeNode*> data;//中序遍历的用户创建的栈
};

/**
 * 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();
 */