653. Two Sum IV - Input is a BST
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
My Accepted Solution
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;
}
};
4.1 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);
}
};