## 题目描述

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``````

## 解法一

### Python

``````class Solution:
def findTarget(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: bool
"""
candidates = set()
stack = []
while stack or root:
if root:
val = root.val
if val in candidates:
return True
else:
stack.append(root)
root = root.left
else:
node = stack.pop()
root = node.right
return False``````

### Java

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean findTarget(TreeNode root, int k) {
Set<Integer> candidates = new HashSet<>();
Stack<TreeNode> stack = new Stack<>();
while (!stack.empty() || root != null) {
if (root != null) {
int val = root.val;
if (candidates.contains(val)) {
return true;
} else {
}
root = root.left;
} else {
TreeNode node = stack.pop();
root = node.right;
}
}
return false;
}
}``````

### C++

``````/**
* 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> candidates;
stack<TreeNode *> sta;
while (!sta.empty() || root != nullptr) {
if (root != nullptr) {
int val = root->val;
if (candidates.find(val) != candidates.end()) {
return true;
} else {
candidates.insert(k - val);
}
sta.push(root);
root = root->left;
} else {
TreeNode *node = sta.top();
sta.pop();
root = node->right;
}
}
return false;
}
};``````