題目傳送門
思路:
周遊一下樹(我這裡用的層序周遊),然後将目标值k-目前節點的值所得到的內插補點存入unordered_set這個hashset,然後周遊的時候驗證目前節點是否在hashset裡面,如果存在的話說明這個節點就是之前期望的內插補點。
/**
* 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 findTarget(TreeNode* root, int k)
{
unordered_set<int> us;
queue<TreeNode*> q;
if(root==NULL)
return false;
q.push(root);
while(!q.empty())
{
TreeNode* f=q.front();
int temp=f->val;
if(us.find(temp)!=us.end())
{
return true;
}
us.insert(k-temp);
if(f->left!=NULL)
q.push(f->left);
if(f->right!=NULL)
q.push(f->right);
q.pop();
}
return false;
}
};