Binary Search Tree Iterator

• LeetCode版

Java

public class BSTIterator {
    
    private Stack<TreeNode> stack = new Stack<>();

    public BSTIterator(TreeNode root) {
        TreeNode cur = root;
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
    }

    public boolean hasNext() {
        return !stack.isEmpty();
    }
    
    public int next() {
        TreeNode ans = stack.pop();
        TreeNode cur = ans.right;
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        return ans.val;
    }
}

• LintCode版

Java

public class BSTIterator {
    
    private Stack<TreeNode> stack = new Stack<>();

    public BSTIterator(TreeNode root) {
        TreeNode cur = root;
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
    }

    public boolean hasNext() {
        return !stack.isEmpty();
    }
    
    public TreeNode next() {
        TreeNode ans = stack.pop();
        TreeNode cur = ans.right;
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        return ans;
    }
}