653. Two Sum IV - Input is a BST ---------E

Q:

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

 

A:

/**
 * 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> S;
        return helper(S, root, k);
    }
private:
    bool helper(unordered_set<int> &S, TreeNode* root, int k) {
        if(root == nullptr){
            return false;
        }
        if(S.find(k-root->val) != S.end())
            return true;
        S.insert(root->val);
        return helper(S, root->left, k) || helper(S, root->right, k);
    }
};