# 653. Two Sum IV - Input is a BST

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

Example 1:

``````Input:
5
/ \
3   6
/ \   \
2   4   7

Target = 9

Output: True
``````

Example 2:

``````Input:
5
/ \
3   6
/ \   \
2   4   7

Target = 28

Output: False
``````

``````class Solution {
public:
bool findTarget(TreeNode* root, int k) {
unordered_set<int> st;
return helper(root, k, st);
}
bool helper(TreeNode* node, int k, unordered_set<int>& st) {
if (!node) return false;
if (st.count(k - node->val)) return true;
st.insert(node->val);
return helper(node->left, k, st) || helper(node->right, k, st);
}
};
``````

``````class Solution {
public:
bool findTarget(TreeNode* root, int k) {
if (!root) return false;
unordered_set<int> st;
queue<TreeNode*> q{{root}};
while (!q.empty()) {
auto t = q.front(); q.pop();
if (st.count(k - t->val)) return true;
st.insert(t->val);
if (t->left) q.push(t->left);
if (t->right) q.push(t->right);
}
return false;
}
};
``````

``````class Solution {
public:
bool findTarget(TreeNode* root, int k) {
vector<int> nums;
inorder(root, nums);
for (int i = 0, j = (int)nums.size() - 1; i < j;) {
if (nums[i] + nums[j] == k) return true;
(nums[i] + nums[j] < k) ? ++i : --j;
}
return false;
}
void inorder(TreeNode* node, vector<int>& nums) {
if (!node) return;
inorder(node->left, nums);
nums.push_back(node->val);
inorder(node->right, nums);
}
};
``````

Two Sum III - Data structure design

Two Sum II - Input array is sorted

Two Sum

https://leetcode.com/problems/two-sum-iv-input-is-a-bst/

https://leetcode.com/problems/two-sum-iv-input-is-a-bst/discuss/106090/my-c-python-solution

https://leetcode.com/problems/two-sum-iv-input-is-a-bst/discuss/106059/JavaC%2B%2B-Three-simple-methods-choose-one-you-like

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation