【LeetCode問題解】173.二叉探索木反復器

ツリー反復器を2つのフォークで検索します.ツリーのルートノードを検索して反復器を初期化します.
next()を呼び出すと、二叉検索ツリーの次の最小数が返されます.
ヒント:next() および hasNext() 操作の時間的複雑さは O(1)を使用 O(h)メモリ、そのうち h 木の高さです.君は仮定できる next() 呼び出しは常に有効であり、すなわちnext()を呼び出すと の場合、BSTには少なくとも次の最小数が存在する.
問題:

二二叉探索ツリーについて二叉探索ツリーの次の最小数=を返す 中間パスシーケンス

のシーケンシャルループ= left - visit - right、非再帰時に補助スタック

を使用する

 left - visit:ルートノードから、ノードおよび左サブツリーノードが順次スタック

に入る

- right:左サブツリーまたは左サブツリーがアクセスされていません.スタック、右サブツリーノードも二叉検索ツリーのrootです.再帰処理

class BSTIterator {
    //     
    Stack s = new Stack<>();
    public BSTIterator(TreeNode root) {
        //
        dfs(root);
    }
    
    /** @return the next smallest number */
    public int next() {
        TreeNode tmp = s.pop();
        //         -right 
        int ret = tmp.val;
        if(tmp.right!=null){
            //     ，        
            dfs(tmp.right);
        }
        return ret;
    }
    
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        if(!s.empty()){
            return true;
        }else{
            return false;
        }
    }
    //         left-visit
    void dfs(TreeNode root){
        while(root!=null){
            s.push(root);
            root = root.left;
        }
    }
}