JAVAプログラム設計:二叉探索木反復器(LeetCode:173)

ツリー反復器を2つのフォークで検索します.ツリーのルートノードを検索して反復器を初期化します.
next()を呼び出すと、二叉検索ツリーの次の最小数が返されます.
 
例:
BSTIterator iterator = new BSTIterator(root); iterator.next();    //3 iterator.next()を返します.   //は、7 iterator.hasNext();//を返します.true iterator.next()を返します.   //は、9 iterator.hasNext();//を返します.true iterator.next()を返します.   //15 iterator.hasNext();//を返します.true iterator.next()を返します.   //は、20 iterator.hasNext();//を返します.falseを返す 
ヒント:
next() および hasNext() 操作の時間的複雑さは O(1)を使用 O(h)メモリ、そのうち h 木の高さです.君は仮定できる next() 呼び出しは常に有効であり、すなわちnext()を呼び出すと の場合、BSTには少なくとも次の最小数が存在する.
構想:もしこの問題の空間複雑度がO(n)であることを示すならば1本の中序遍歴テンプレート問題であるが、空間複雑度はO(h)であり、hは木の高さであるため、私たちはどのようにもっと少ない空間を使ってこの問題を完成するかを考えなければならない.もちろん、私たちは中序遍歴から逃れられないに違いない.ただ、私たちは一度にすべての要素をスタックに入れる必要はない.最小値要素を見つけてから、パス上のすべてのノードをスタックに押し込み、next関数を呼び出すたびにスタックトップ要素の値になることを考慮することができます.hasnextの呼び出しは、スタックが空であるかどうかを判断することです.

class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) { val = x; }
 }
 
class BSTIterator {

	TreeNode root;
	Stack st; 
    public BSTIterator(TreeNode root) {
        this.root=root;    
    	this.st=new Stack<>();
    	while(this.root!=null)
    	{
    		st.push(this.root);
    		this.root=this.root.left;
    	}
    }
    
    /** @return the next smallest number */
    public int next() {
    	TreeNode cur=st.peek(); st.pop();
    	int res=cur.val;
    	cur=cur.right;
    	while(cur!=null)
    	{
    		st.push(cur);
    		cur=cur.left;
    	}
    	return res;
    }
    
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !st.isEmpty();
    }
}

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator obj = new BSTIterator(root);
 * int param_1 = obj.next();
 * boolean param_2 = obj.hasNext();
 */