二叉树非递归遍历

Binary Search Tree Iterator

实现hasNext和next两个方法

这个主要就需要背了

非递归需要实现栈

这个栈的定义是栈内元素是所有路径上的元素

这个实现比较灵活，这样通过把right和left互换，实现prev操作找前继结点

另一种非递归的实现

一个节点一旦被print过，就可以不在存stack里面了，直接pop

省耗费

栈存所有没被访问过得点

这个方法需要阅读全文并倒背如流

class BSTIterator {
    private Stack<TreeNode> stack;
    
    public BSTIterator(TreeNode root) {
        stack = new Stack<>();
        findMostLeft(root);
    }
    
    private void findMostLeft(TreeNode node) {
        while (node != null) {
            stack.add(node);
            node = node.left;
        }
    }
    
    public boolean hasNext() {
        return stack.isEmpty();
    }
    
    public TreeNode next() {
        TreeNode node = stack.pop();
        if (node.right != null) {
            findMostLeft(node.right);
        }
        return node;
    }
}