LeetCode 173. Binary Search Tree Iterator

中順遍歴.
スタックで保存されたノードは、常にnext()にアクセスされていないレイヤの最小ノードであり、以下のように初期化されます.

        for ( ; root != nullptr; root = root->left)
        {
            stk.push(root);
        }

nextが反復器に移行するたびに、削除されたノードの左サブツリーが空(以前に反復された)であることを意味し、右サブツリーの最も左のパスのすべてのノードをスタックに追加します.
コード:

class BSTIterator 
{
public:
    BSTIterator(TreeNode *root) 
    {
        for ( ; root != nullptr; root = root->left)
        {
            stk.push(root);
        }
    }

    /** @return whether we have a next smallest number */
    bool hasNext() 
    {
        return !stk.empty();
    }

    /** @return the next smallest number */
    int next() 
    {
        auto node = stk.top();
        int val = node->val;
        stk.pop();
        node = node->right;
        for ( ; node != nullptr; node = node->left)
        {
            stk.push(node);
        }
        return val;
    }

private:
    stack<TreeNode*> stk;
};

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

くうかんふくざつさ
next()では、各ノードがforループを呼び出し、右サブツリーの最左パスを押し込むと、左サブツリーが空であることが保証されています(スタックに左サブツリーが存在しないノード)
したがってスタックの深さはツリーの深さを超えず,空間複雑度はO(h)である.
時間の複雑さ
hasNext()の時間的複雑度は明らかにO(1)である.
next()を考察し,償却解析を行い,演算はnext()のforサイクルに集中し,ツリーの各ノードはスタックに1回のみ押し込まれること,すなわちforサイクルのpushはO(N)回のみ実行され,ここでNはツリーのノード数であることに気づいた.
従ってnext毎の時間複雑度はO(N)/N=O(1)である.