二叉搜索树迭代器 II

/*
 * Leetcode 1586: 二叉搜索树迭代器 II
 *
 * 题目思路：
 * 1. 使用Java Stream API，我们仍需要对树进行中序遍历并存储结果。
 * 2. 可以利用Stream的collect()方法来将中序遍历的节点收集到List中。
 * 3. 其他逻辑与普通Java实现类似。
 */

import java.util.List;
import java.util.ArrayList;
import java.util.stream.Collectors;
import java.util.stream.Stream;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class BSTIteratorStream {
    private List<TreeNode> inorderList;
    private int currentIndex;

    public BSTIteratorStream(TreeNode root) {
        inorderList = new ArrayList<>();
        inorderList = inorderTraversal(root).collect(Collectors.toList());
        currentIndex = -1;
    }

    // 使用Stream进行中序遍历
    private Stream<TreeNode> inorderTraversal(TreeNode node) {
        if (node == null) return Stream.empty();
        return Stream.concat(
            Stream.concat(inorderTraversal(node.left), Stream.of(node)),
            inorderTraversal(node.right)
        );
    }

    public boolean hasNext() {
        return currentIndex + 1 < inorderList.size();
    }

    public TreeNode next() {
        if (!hasNext()) throw new IllegalStateException("No next element");
        currentIndex++;
        return inorderList.get(currentIndex);
    }

    public boolean hasPrev() {
        return currentIndex - 1 >= 0;
    }

    public TreeNode prev() {
        if (!hasPrev()) throw new IllegalStateException("No previous element");
        currentIndex--;
        return inorderList.get(currentIndex);
    }
}