Two Sum IV - Input is a BST

题目
Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.

答案

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public class BSTIteratorInorder {

        Stack<TreeNode> stk = new Stack<TreeNode>();
        TreeNode currSmallest;
        public BSTIteratorInorder(TreeNode root) {
            if(root == null) return;
            pushleft(root);
        }

        /** @return whether we have a next smallest number */
        public boolean hasNext() {
            return stk.size() > 0;
        }

        /** @return the next smallest number */
        public TreeNode next() {
            TreeNode top = stk.pop();
            int ret = top.val;
            pushleft(top.right);
            return top;
        }

        public void pushleft(TreeNode subroot) {
            while(subroot != null) {
                stk.push(subroot);
                subroot = subroot.left;
            }
        }
    }

    public class BSTIteratorReverseInorder {

        Stack<TreeNode> stk = new Stack<TreeNode>();
        TreeNode currSmallest;
        public BSTIteratorReverseInorder(TreeNode root) {
            if(root == null) return;
            pushright(root);
        }

        /** @return whether we have a next smallest number */
        public boolean hasNext() {
            return stk.size() > 0;
        }

        /** @return the next smallest number */
        public TreeNode next() {
            TreeNode top = stk.pop();
            int ret = top.val;
            pushright(top.left);
            return top;
        }

        public void pushright(TreeNode subroot) {
            while(subroot != null) {
                stk.push(subroot);
                subroot = subroot.right;
            }
        }
    }


    public boolean findTarget(TreeNode root, int k) {
        if(root.left == null && root.right == null) return false;
        BSTIteratorInorder itr1 = new BSTIteratorInorder(root);
        BSTIteratorReverseInorder itr2 = new BSTIteratorReverseInorder(root);

        TreeNode leftnode = itr1.next();
        TreeNode rightnode = itr2.next();

        while(itr1.hasNext()) {
            if(leftnode == rightnode) return false;

            int sum = leftnode.val + rightnode.val;
            if(sum == k) {
                return true;
            }
            else if(sum > k) {
                rightnode = itr2.next();
            }
            else {
                leftnode = itr1.next();
            }
        }
        return false;
    }
}