Binary Search Tree Iterator - LeetCode

算法

中序遍历，用栈保存需要回溯的节点的列表，这个列表最大为树的高度h，所以空间复杂度为O(h)

class BSTIterator {
public:
    vector<TreeNode*> vec;
    BSTIterator(TreeNode *root) {
        while(root)
        {
            vec.push_back(root);
            root = root -> left;
        }
    }
    /** @return whether we have a next smallest number */
    bool hasNext() {
        return !vec.empty();
    }
    /** @return the next smallest number */
    int next() {
        TreeNode *cur = vec.back(); vec.pop_back(); //回溯
        int ret = cur -> val;
        if(cur->right) // 被回溯的节点有右子树，那么就将右孩子到右子树最左节点路径的节点全部压栈
        {
            cur = cur -> right;
            while(cur)
            {
                vec.push_back(cur);
                cur = cur->left;
            }
        }
        return ret;
    }
};