Binary Search Tree Iterator(中序遍历)

题目

题意

写一个二叉搜索树的迭代器，包括初始化、next()和hasNext()操作，要求平摊时间复杂度为O(1)，空间复杂度为O(h)

分析

因为空间复杂度是O(h)，所以肯定不能把整个树直接存成一个数组然后直接查找，而是要利用树的性质。与所有遍历一样，中序遍历的实质功能也可理解为，为所有节点赋予一个次序，从而将半线性的二叉树转化为线性结构。于是一旦指定了遍历策略，即可与向量和列表一样，在二叉树的节点之间定义前驱与后继关系。其中没有前驱（后继）的节点称作首（末）节点。

对于后继的查找，共分两大类情况。若当前节点有右孩子，则其直接后继必然存在，且属于其右子树。此时只需转入右子树，再沿该子树的最左侧通路朝左下方深入，直到抵达子树中最靠左（最小）的节点。

反之，若当前节点没有右子树，则若其直接后继存在， 必为该节点的某一祖先，且是将当前节点纳入其左子树的最低祖先。于是首先沿右侧通路朝左上方上升，当不能继续前进时，再朝右上方移动一步即可。

作为后一情况的特例，出口时s可能为NULL。这意味着此前沿着右侧通路向上的回溯，抵达了树根。也就是说，当前节点是全树右侧通路的终点——它也是中序遍历的终点，没有后继。

代码

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class BSTIterator {
public:
    stack<TreeNode *> s;
    void addToStack(TreeNode * root){
        while(root){
            s.push(root);
            root=root->left;
        }
    }

    BSTIterator(TreeNode *root) {
        addToStack(root);
    }

    /** @return whether we have a next smallest number */
    bool hasNext() {
        return s.size()>0;
    }

    /** @return the next smallest number */
    int next() {
        int res = s.top()->val;
        TreeNode * top = s.top();
        s.pop();
        if(top-> right){
            addToStack(top->right);
        }

        return res;
    }
};

/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = BSTIterator(root);
 * while (i.hasNext()) cout << i.next();
 */

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 yxhlfx@163.com