Meng

173. Binary Search Tree Iterator

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST. Calling next() will return the next smallest number in the BST.

Example

BSTIterator iterator = new BSTIterator(root);
iterator.next();    // return 3
iterator.next();    // return 7
iterator.hasNext(); // return true
iterator.next();    // return 9
iterator.hasNext(); // return true
iterator.next();    // return 15
iterator.hasNext(); // return true
iterator.next();    // return 20
iterator.hasNext(); // return false

题意：这道题是说要写一个 BST 的 tree iterator。 有两种解法。第一种比较直观就直接中序遍历一下，把节点存在 list 里面即可。 第二中解法就是用栈来模拟一下中序递归。因为中序递归输出的第一个元素永远是 leftmost，所以我们一开始就压栈, 压到最左处的节点。 当我们 pop 出来一个节点的话，如果其还有右节点，那么我们需要重复操作，直到压到最左节点。

代码

class BSTIterator {
    Stack<TreeNode> stack = new Stack<>();
    public BSTIterator(TreeNode root) {
        while(root != null) {
            stack.add(root);
            root = root.left;
        }
    }

    /** @return the next smallest number */
    public int next() {
        TreeNode cur = stack.pop();
        int ret = cur.val;
        cur = cur.right;
        while(cur != null) {
            stack.add(cur);
            cur = cur.left;
        }
        return ret;
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !stack.isEmpty();
    }
}

Search

    Table of Contents