首页 > 代码库 > Leetcode:Binary Search Tree Iterator

Leetcode:Binary Search Tree Iterator

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.

分析:

这是一个类似设计的题,这种题看上去虽然繁琐,但其考察的算法一般相对简单些,解决此题的关键根据从题目要求写出能满足要求的算法。根据题意,hasNext()的功能很容易理解,next()的功能具体说来应该是每调用一次便返回小于上次返回值的最小值,第一次调用返回的是BST中最小的值。一个很naive的解法是中序遍历BST,然后把遍历序列存在一个queue中,每次调用next(),从queue中pop出一个元素返回;hasNext()函数可以用判断queue是否为空来实现。但这个解法有个问题,就是用到的memory是O(n),因为我们保存了整个的中序遍历序列。虽然空间复杂度不满足要求,但可以在leetcode测试通过,代码如下:

class BSTIterator {public:    BSTIterator(TreeNode *root) {        if(root != NULL){            inorder_traversal(root);        }    }    /** @return whether we have a next smallest number */    bool hasNext() {        if(!s.empty()) return true;        return false;    }    /** @return the next smallest number */    int next() {        int next_small = s.front();        s.pop();        return next_small;    }private:    queue<int> s;    void inorder_traversal(TreeNode *root){        if(root == NULL) return;        inorder_traversal(root->left);        s.push(root->val);        inorder_traversal(root->right);    }};/** * Your BSTIterator will be called like this: * BSTIterator i = BSTIterator(root); * while (i.hasNext()) cout << i.next(); */

如果满足O(h)的memory要求,我们可以用类似跌代版中序遍历的方法,用一个stack做存储,取stack的顶元素,如果该元素有右孩子则把该右孩子最左的路径的节点压入stack。由于每个节点被压入和弹出stack一次,所以next()的amortized time complexity应该为O(1)。代码如下:

class BSTIterator {public:    BSTIterator(TreeNode *root) {        for(TreeNode *p = root; p; p = p->left)            s.push(p);    }    /** @return whether we have a next smallest number */    bool hasNext() {        if(!s.empty()) return true;        return false;    }    /** @return the next smallest number */    int next() {        TreeNode *tmp = s.top();        s.pop();        for(TreeNode *p = tmp->right; p; p = p->left)            s.push(p);        return tmp->val;    }private:    stack<TreeNode *> s;};

 

Leetcode:Binary Search Tree Iterator