[Java] Use iterator


  • 0
    D

    Time : O(n) Space: O(log(n))

    class Iterator {
        boolean minIter = true;
        Stack<TreeNode> stack = new Stack<>();
        Iterator(TreeNode root, boolean min) {
            minIter = min;
            pull(root);
        }
        
        int next() {
            TreeNode node = stack.pop();
            if (minIter) {
                if (node.right != null) pull(node.right);
            } else {
                if (node.left != null) pull(node.left);
            }
            return node.val;
        }
        
        boolean hasNext() {
            return stack.isEmpty() == false;
        }
        
        int peek() {
            return stack.peek().val;
        }
    
        void pull(TreeNode node) {
            while(node != null) {
                stack.push(node);
                if (minIter) node = node.left;
                else node = node.right;
            }
        }
    }
    
    public boolean findTarget(TreeNode root, int k) {
        if (root == null) return false;
        Iterator minIter = new Iterator(root, true);
        Iterator maxIter = new Iterator(root, false);
        while(minIter.hasNext() && maxIter.hasNext()) {
            if (minIter.peek() == maxIter.peek()) return false;
            
            if(minIter.peek() + maxIter.peek() == k) {
                return true;
            } else if (minIter.peek() + maxIter.peek() < k) {
                minIter.next();
            } else {
                maxIter.next();
            }
        }
        return false;
    }

Log in to reply
 

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