173. 二叉搜索树迭代器

Problem: 173. 二叉搜索树迭代器

思路

本题的核心关键就是用栈来实现递归。只要用栈模拟了二叉搜素树的中序遍历，就可以迭代返回需要的节点值。

我们考察递归的过程，在中序遍历时，会不断调用左节点的递归函数，直到左子树完成递归。因此，我们需要用一个栈来保存这个递归过程。即我们用栈来存储正在访问左子树，但是本身以及右子树还未访问的节点。

当左子树完成递归后，栈顶元素就是当前节点，我们弹出该节点，并获得当前位置的值。

接下来考虑，我们要如何模拟调用右递归函数呢？

可能我们会直观地猜想需要再用一个栈来存储，但实际上并不需要。

因为当我们调用右递归函数时，递归函数会继续调用左递归函数，也就意味着并没有连续递归调用的过程，因此我们也就不需要一个栈来存储。

我们模拟右递归调用，关键是要能使得当前节点在有无右子树的情况下都能正确处理，即：

1. 在无右子树的情况下，返回到父节点。
2. 在有右子树的情况下，返回到当前节点的右节点。

如果直接用栈顶元素，能否达到这个效果？显然是不行的，因为当无右子树时，我们显然不做操作，这时栈顶元素是其父节点，下一次操作会访问其父节点的左子树，造成循环访问。

因此我们需要设置一个变量current，以表示当前访问的节点。我们以current为核心，先“递归”访问左子树，然后弹出并输出栈顶元素，最后在next()结束时把curren设为其右节点，这样就把”递归”引向了其右子树，完整地模拟了一次递归。

Code

/**
 * 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 {
    int val;
    // 模拟中序遍历，存储当前子树递归中未返回的左调用
    Deque<TreeNode> stack = new ArrayDeque();
    // 中序遍历的右调用
    TreeNode current;
    public BSTIterator(TreeNode root) {
        val = -1;
        current = root;
    }
    
    public int next() {
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        TreeNode ret = stack.pop();
        current = ret.right;
        return ret.val;
    }
    
    public boolean hasNext() {
        return current != null || !stack.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();
 */