653. Two Sum IV - Input is a BST

Version #1 写了两个iterator
其实感觉可以不写
直接用两个stack也可以

47.27 %
class InorderIterator implements Iterator<TreeNode> {
    Stack<TreeNode> stack;
    public InorderIterator(TreeNode root) {
        TreeNode curr = root;
        stack = new Stack<>();
        pushAll(curr);
    }
    @Override
    public boolean hasNext() {
        return !stack.isEmpty();
    }
    @Override
    public TreeNode next() {
        TreeNode curr = stack.pop();
        TreeNode result = curr;
        curr = curr.right;
        pushAll(curr);
        return result;
    }

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

class ReverseInorderIterator implements Iterator<TreeNode> {
    Stack<TreeNode> stack;
    public ReverseInorderIterator(TreeNode root) {
        TreeNode curr = root;
        stack = new Stack<>();
        pushAll(curr);
    }
    @Override
    public boolean hasNext() {
        return !stack.isEmpty();
    }
    @Override
    public TreeNode next() {
        TreeNode curr = stack.pop();
        TreeNode result = curr;
        curr = curr.left;
        pushAll(curr);
        return result;
    }

    private void pushAll(TreeNode curr) {
        while (curr != null) {
            stack.push(curr);
            curr = curr.right;
        }
    }
}
public class Solution {

    public boolean findTarget(TreeNode root, int k) {
        InorderIterator inorderIterator = new InorderIterator(root);
        ReverseInorderIterator reverseInorderIterator = new ReverseInorderIterator(root);
        TreeNode left = inorderIterator.next();
        TreeNode right = reverseInorderIterator.next();
        while (inorderIterator.hasNext() && reverseInorderIterator.hasNext()) {
            //System.out.println(left.val + " " + right.val);
            if (left == right) return false;
            if (left.val + right.val == k) return true;
           
            if (left.val + right.val < k) {
                left = inorderIterator.next();
            } else {
                right = reverseInorderIterator.next();
            }
        }
        return false;
    }
}