题目描述:
给定一个二叉搜索树和一个目标结果,如果 BST 中存在两个元素且它们的和等于给定的目标结果,则返回 true。
案例 1:
输入:
5
/ \
3 6
/ \ \
2 4 7
Target = 9
输出: True
案例 2:
输入:
5
/ \
3 6
/ \ \
2 4 7
Target = 28
输出: False
想的有点复杂,以为是背包问题,使所有节点都做一次root,然后每次加和都要包括root。但显然这道题不是让每个节点都做一次root并且也不是必须包含root节点在内,包含root的话,就必须要求两个数在同一棵子树上,想法错误。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
//以当前节点为根,并且选择根
bool traverse(TreeNode* root,int k,int num,int sum){
if(root==NULL||num>2||sum>k)
return false;
if(k==sum)
return true;
return traverse(root->left,k,num+1,sum+root->val)||traverse(root->right,k,num+1,sum+root->val);
}
bool findTarget(TreeNode* root, int k) {
if(root==NULL||k==0)
return false;
queue<TreeNode*> q;
q.push(root);
bool flag=false;
while(!q.empty()){
TreeNode* now=q.front();
q.pop();
bool temp=traverse(now,k,0,0);//traverse(树,和,数的个数,当前数的和)
if(now->left)
q.push(now->left);
if(now->right)
q.push(now->right);
flag=(temp||flag);
}
return flag;
}
};
正确思路:遍历树,将树中元素都存放到vector中,然后遍历vector,查找是否存在两个数的加和==k,此处还是用查找差值的方法查找第二个数。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void inorder(TreeNode* root,vector<int> &res){
if(root==NULL)
return ;
inorder(root->left,res);
res.push_back(root->val);
inorder(root->right,res);
}
bool findTarget(TreeNode* root, int k) {
if(root==NULL||k==0)
return false;
vector<int> res;
inorder(root,res);
for(vector<int>::iterator it=res.begin();it!=res.end();it++){
int tar=k-(*it);
//有一点需要注意,不能重复查找,即查找到的第二个元素不能是第一个元素
if((find(res.begin(),res.end(),tar)!=res.end())&&(find(res.begin(),res.end(),tar)!=it))//find(res.begin(),res.end(),tar)查找起点到终点区间内的目标值,返回迭代器
//count(res.begin(),res.end(),tar)查找起点到终点区间内的目标值,返回目标元素的个数
return true;
}
return false;
}
};