Java Solution : O(n) time and O(height) space, Iterative


  • 0
    T
            if (root == null) {
                return false;
            }
            Deque<TreeNode> left = new LinkedList<>();
            Deque<TreeNode> right = new LinkedList<>();
            TreeNode currLeft = root;
            TreeNode currRight = root;
            while (currLeft != null) {
                left.offerFirst(currLeft);
                currLeft = currLeft.left;
            }    
            while (currRight != null) {
                right.offerFirst(currRight);
                currRight = currRight.right;
            }
            while (!left.isEmpty() && !right.isEmpty() && left.peekFirst() != right.peekFirst()) {
                int sum = left.peekFirst().val + right.peekFirst().val;
                if (sum == k) {
                    return true;
                }
                if (sum < k) {
                    currLeft = left.pollFirst();
                    currLeft = currLeft.right;
                    while (currLeft != null) {
                        left.offerFirst(currLeft);
                        currLeft = currLeft.left;
                    }
                } else {
                    currRight = right.pollFirst();
                    currRight = currRight.left;
                    while (currRight != null) {
                        right.offerFirst(currRight);
                        currRight = currRight.right;
                    }
                }    
            }
            return false;
        }    ```

Log in to reply
 

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