Java O(1) space O(log n) time 21ms solution runtime beats 100%


  • 0
    Y

    Based on BST search

    class Solution {
        public boolean findTarget(TreeNode root, int k) {
            TreeNode aNode = root, bNode = root;
            while (aNode.left != null) aNode = aNode.left;
            while (bNode.right != null) bNode = bNode.right;
            while (aNode != null && bNode != null && aNode != bNode) {
                int a = aNode.val, b = bNode.val;
                int sum = a + b;
                if (sum == k)
                    return true;
                else if (sum < k) {
                    // find smallest bigger than k-b
                    int complement = k - b;
                    if (complement >= b)
                        return false;
                    aNode = null;
                    TreeNode x = root;
                    while (x != null) {
                        if (x.val == complement)
                            return true;
                        else if (x.val < complement)
                            x = x.right;
                        else if (x.val > complement) {
                            aNode = x;
                            x = x.left;
                        }
                    }
                } else {
                    // find biggest smaller than k-a
                    int complement = k - a;
                    if (complement <= a)
                        return false;
                    bNode = null;
                    TreeNode x = root;
                    while (x != null) {
                        if (x.val == complement)
                            return true;
                        else if (x.val > complement)
                            x = x.left;
                        else {
                            bNode = x;
                            x = x.right;
                        }
                    }
                }
            }
            return false;
        }
    }
    

Log in to reply
 

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