题目描述
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.
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
Constraints:
- The number of nodes in the tree is in the range [1, 104].
- -10^4 <= Node.val <= 10^4
- root is guaranteed to be a valid binary search tree.
- -10^5 <= k <= 10^5
解题思路
- 本质是Two Sum的变形
- 我们遍历一个节点，然后查看集合是否有对应的节点
- 可是使用层次遍历或者递归搜索
C++代码 层次遍历
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool findTarget(TreeNode* root, int k) {
unordered_set<int> sets;
if(root == nullptr){
return false;
}
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
int size = q.size();
TreeNode* node = q.front();
q.pop();
if(sets.count(k - node -> val) != 0){
return true;
}
sets.insert(node -> val);
if(node -> left){
q.push(node -> left);
}
if(node -> right){
q.push(node -> right);
}
}
return false;
}
};
C++代码 深度优先搜索
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool helper(TreeNode* node, int k, unordered_set<int>& sets){
if(node == nullptr){
return false;
}
if(sets.count(k - node -> val) != 0){
return true;
}
sets.insert(node -> val);
return helper(node -> left, k, sets) || helper(node -> right, k, sets);
}
bool findTarget(TreeNode* root, int k) {
unordered_set<int> sets;
return helper(root, k, sets);
}
};
