*LeetCode-Binary Search Tree Iterator

802 단어
데이터 구 조 를 설계 하고 내부 의 stack 으로 루트 보다 작은 노드 를 저장 합 니 다. 즉, push 의 순 서 는 크 고 작은 것 입 니 다. 하나의 pushall 함 수 를 실현 하 는 것 은 push 라 는 node 가 왼쪽으로 가 는 경로 의 모든 노드 입 니 다.
public class BSTIterator {
    private Stack<TreeNode> stack = new Stack<TreeNode>();
    public BSTIterator(TreeNode root) {
        pushAll(root);
    }
    private void pushAll(TreeNode node) {
        while ( node != null ){
            stack.push(node);
            node = node.left;
        }
    }
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !stack.isEmpty();
    }

    /** @return the next smallest number */
    public int next() {
        TreeNode cur = stack.pop();
        pushAll(cur.right);
        return cur.val;
    }
}

좋은 웹페이지 즐겨찾기