Concise Java Solution O(n) time, O(h) space, using two stacks.


  • 0
    F

    If the given data structure is a sorted array, we could easily come up with the two-pointer solution. When it comes to a BST, similar idea could be used to solve the problem. In this case, we can use a stack to find next smaller value and another stack to find next large value(similar to BST iterator, but we only implement next()). Let the code explains:

    public class Solution {
        public boolean findTarget(TreeNode root, int k) {
            Stack<TreeNode> small = new Stack<>();
            Stack<TreeNode> large = new Stack<>();
            
            initialStack(small, true, root);
            initialStack(large, false, root);
            
            TreeNode nextSmall = getNext(large, false);
            TreeNode nextLarge = getNext(small, true);
            
            while (nextSmall != null && nextLarge != null && nextSmall != nextLarge) {
                int sum = nextSmall.val + nextLarge.val;
                
                if (sum == k) {
                    return (true);
                } else if (sum < k) {
                    nextLarge = getNext(small, true);
                } else {
                    nextSmall = getNext(large, false);
                }
            }
            
            return (false);
        }
        
        void initialStack(Stack<TreeNode> stack, boolean small, TreeNode root) {
            while (root != null) {
                stack.push(root);
                root = small ? root.left : root.right;
            }
        }
        
        TreeNode getNext(Stack<TreeNode> stack, boolean small) {
            if (stack.isEmpty()) {
                return (null);
            }
            
            TreeNode res = stack.pop();
            TreeNode node = small ? res.right : res.left;
            
            while (node != null) {
                stack.push(node);
                node = small ? node.left : node.right;
            }
            
            return (res);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.