653. Two Sum IV - Input is a BST

2020, Nov 22 2 mins read

1. Description

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

2. Example

Example 1

Input: root = [5,3,6,2,4,null,7], k = 9
Output: true

Example 2

Input: root = [5,3,6,2,4,null,7], k = 28
Output: false

Example 3

Input: root = [2,1,3], k = 4
Output: true

Example 4

Input: root = [2,1,3], k = 1
Output: false

Example 5

Input: root = [2,1,3], k = 3
Output: true

3. Constraints

The number of nodes in the tree is in the range [1, 10$^{4}$].
-10$^{4}$ <= Node.val <= 10$^{4}$
root is guaranteed to be a valid binary search tree.
-10$^{5}$ <= k <= 10$^{5}$

4. Solutions

Two Pointers

n is the number of nodes in i_root
Time complexity: O(n)
Space complexity: O(n)

class Solution
{
private:
    vector<int> orderedValues;

    void preorderTraverse(TreeNode *i_root)
    {
        if(i_root->left) preorderTraverse(i_root->left);

        orderedValues.push_back(i_root->val);

        if(i_root->right) preorderTraverse(i_root->right);
    }
public:
    // bool findTarget(TreeNode* root, int k)
    bool findTarget(TreeNode *i_root, int sum)
    {
        if(!i_root) return false;

        preorderTraverse(i_root);

        for(int left = 0, right = orderedValues.size() - 1; left < right; )
        {
            if(orderedValues[left] + orderedValues[right] == sum)
                return true;
            else if(orderedValues[left] + orderedValues[right] < sum)
                left++;
            else
                right--;
        }

        return false;
    }
};

Map

n is the number of nodes in i_root
Time complexity: O(n)
Space complexity: O(n)

class Solution
{
private:
    unordered_map<int, int> valuesOccur;
public:
    // // bool findTarget(TreeNode* root, int k)
    bool findTarget(TreeNode *i_root, int sum)
    {
        if(!i_root) return false;
        if(valuesOccur.find(sum - i_root->val) != valuesOccur.end()) return true;

        valuesOccur[i_root->val]++;

        return findTarget(i_root->left, sum) || findTarget(i_root->right, sum);
    }
};