Leetcode173. 二叉搜索树迭代器

空间复杂度O(h)而不是O(n)，因此不能直接在初始化函数中做中序遍历将结果存储到数组中。
next()和hasNext()时间复杂度为O(1)
首先本题很容易想到用二叉树的中序遍历去解决，外加注意点1.我们得到思路：仅仅将中序遍历最小值之前的节点压入栈中，当next时我们将栈顶元素取出即为最小值返回，当然在此之前需要将下一个最小值找到，并将路径上的所有节点压入栈中以供使用，查看是否迭代到头只需判断栈是否为空即可，如下：

class BSTIterator {

private:

      stack<TreeNode*>ss;

public:

    BSTIterator(TreeNode* root) {

        while(root)

        {

            while (root)

            {

                ss.push(root);

                root=root->left;

            }

        }

    }

    /** @return the next smallest number */

    int next() {

         TreeNode* cur=ss.top();

         int num=cur->val;

         ss.pop();

         cur=cur->right;

        while (cur)

        {

            ss.push(cur);

            cur=cur->left;

        }

         return num;

    }

    /** @return whether we have a next smallest number */

    bool hasNext() {

        return !ss.empty();

    }

};

巴特西

Leetcode173. 二叉搜索树迭代器

最新文章

热门文章