# LeetCode-Alg-653-Two Sum IV Input is a BST

## LeetCode-Alg-653-Two Sum IV Input is a BST

Posted by Jae on May 16, 2019

### 1、题目

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


### 3、实现

public class Solution {
public boolean findTarget(TreeNode root, int k) {
List<Integer> res = new ArrayList<>();
inOrderTraversal(root, res);

for (int i = 0; i < res.size(); i++){
if (res.get(i) < k){
int diff = k - res.get(i);
if (diff < res.get(i)){
return false;
}
if (true == binarySearch(k-res.get(i), res, i+1, res.size()-1)){
return true;
}
}
}
return false;
}

// 中序遍历，生成非降序的数组
private void inOrderTraversal(TreeNode root, List<Integer> res){
if (root == null){
return;
}
inOrderTraversal(root.left, res);
inOrderTraversal(root.right, res);
}

// 二分查找
private boolean binarySearch(int k, List<Integer> res, int start, int end){
int low = start;
int high = end;
while (low <= high){
int mid = low + (high - low)/2;
if (res.get(mid) == k){
return true;
}
if (res.get(mid) > k){
high = mid - 1;
}
if (res.get(mid) < k){
low = mid + 1;
}
}
return false;
}
}


### 4、他山之石

#### 4.1、使用HashSet

public class Solution {

// 使用HashSet
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);
}
}


#### 4.2、使用BFS

public class Solution { public boolean findTarget(TreeNode root, int k) { List res = new ArrayList<>(); inOrderTraversal(root, res);

    int low = 0;
int high = res.size() - 1;

while (low < high){
int sum = res.get(low) + res.get(high);
if (sum == k){
return true;
}
if (sum < k){
low++;
}
if (sum > k){
high--;
}
}
return false;
}

private void inOrderTraversal(TreeNode root, List<Integer> res){
if (root == null){
return;
}
inOrderTraversal(root.left, res);