package 二叉树.二叉搜索树;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
/**
 * https://leetcode-cn.com/problems/binary-search-tree-iterator/ _173_二叉搜索树迭代器
 * 
 * @author Huangyujun 迭代器（容器，提前存储了按照一定规则摆放的数据）
 */
public class _173_二叉搜索树迭代器 {
    class BSTIterator {
        // 方法一：定义了一个list 容器存放好结果（递归实现）
        private int idx;
        private List<Integer> arr;
        public BSTIterator(TreeNode root) {
            idx = 0;
            arr = new ArrayList<Integer>();
            inorderTraversal(root, arr);
        }
        public int next() {
            return arr.get(idx++);
        }
        public boolean hasNext() {
            return idx < arr.size();
        }
        private void inorderTraversal(TreeNode root, List<Integer> arr) {
            if (root == null) {
                return;
            }
            inorderTraversal(root.left, arr);
            arr.add(root.val);
            inorderTraversal(root.right, arr);
        }
    }
    // 迭代实现
    class BSTIterator2 {
        private TreeNode cur;
        private Deque<TreeNode> stack;
        public BSTIterator2(TreeNode root) {
            cur = root;
            stack = new LinkedList<TreeNode>();
        }
        public int next() {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            int ret = cur.val;
            cur = cur.right;
            return ret;
        }
        public boolean hasNext() {
            return cur != null || !stack.isEmpty();
        }
    }
}