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

## ้ข็ฎๅฐๅ

https://leetcode.com/problems/two-sum-iv-input-is-a-bst/

## ้ข็ฎๆ่ฟฐ

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

## ไปฃ็ 

### Approach #1 HashSet

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean findTarget(TreeNode root, int k) {
Set<Integer> set = new HashSet();
return find(root, k, set);
}

public boolean find(TreeNode root, int k, Set<Integer> set) {
if (root == null)        return false;
if (set.contains(k - root.val))        return true;

return find(root.left, k, set) || find(root.right, k, set);
}
}``````

### Approach #2 BFS

``````class Solution {
public boolean findTarget(TreeNode root, int k) {
Set<Integer> set = new HashSet();
Queue<TreeNode> queue = new LinkedList();
while (!queue.isEmpty()) {
if (queue.peek() != null) {
TreeNode node = queue.remove();
if (set.contains(k - node.val))        return true;
} else {
queue.remove();
}
}

return false;
}
}``````

### Approach #3 BST

``````class Solution {
public boolean findTarget(TreeNode root, int k) {
List<Integer> list = new ArrayList();
inorder(root, list);
int l = 0, r = list.size() - 1;
while (l < r) {
int sum = list.get(l) + list.get(r);
if (sum == k) {
return true;
}
if (sum < k) {
l++;
} else {
r--;
}
}

return false;
}

public void inorder(TreeNode root, List<Integer> list) {
if (root == null)    return;
inorder(root.left, list);