LeetCode 173. Binary Search Tree Iterator

Problem

LeetCode 173. Binary Search Tree Iterator

1. 题目简述

实现一个二叉搜索树(BST树)的iterator类，其中包含next函数和hasNext函数。例如：

Example:

    7 
  /   \ 
 3    15 
     /  \   
    9   20 

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

2. 算法思路

这又是一道关于设计的题目，很明显，最直接的方法，就是使用List按照中序遍历的顺序存储所有的节点，然后记录当前的index。

根据讨论区大佬的解法，这里还可以用到stack来帮助我们动态地来计算next节点，而不是一次性遍历所有。

为什么想到要用栈呢？因为就像非递归形式的中序遍历一样的想法，需要用到栈来帮助回溯到父节点。

或许还可以用Morris遍历？

3. 解法：

1. 使用List，很笨，但很直接

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class BSTIterator {

    List<Integer> values;
    int index;

    private void getValues(TreeNode root, List list) {
        if (root == null) {
            return;
        }

        // fe非递归形式中序遍历i
        // Stack<TreeNode> stack = new Stack<TreeNode>();
        // stack.push(root);

        // while (！stack.isEmpty() || root == null) {
        //     if (root == null) {
        //         root = stack.pop();
        //         values.add(root.val);
        //         root = root.right;
        //     } else {
        //         stack.push(root);
        //         root = root.left;
        //     }
        // }

        if (root.left != null) {
            getValues(root.left, list);
        }
        list.add(root.val);
        if (root.right != null) {
            getValues(root.right, list);
        }
    }

    public BSTIterator(TreeNode root) {
        values = new ArrayList();
        getValues(root, values);
        index = -1;
    }

    /** @return the next smallest number */
    public int next() {
        int size = values.size();
        if (++index < size) {
            return values.get(index);
        } else {
            return Integer.MIN_VALUE;
        }
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        if (index + 1 < values.size()) {
            return true;
        } else {
            return false;
        }
    }
}

/**
 * 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();
 */

2. 使用Stack来帮助动态进行找next节点

class BSTIterator {

    Stack<TreeNode> stack = new Stack<TreeNode>();

    private void pushNodes(TreeNode root) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
    }

    public BSTIterator(TreeNode root) {
        pushNodes(root);
    }

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

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