# C#LeetCode刷题之#653-两数之和 IV – 输入 BST（Two Sum IV – Input is a BST）

5
/ \
3   6
/ \   \
2   4   7

Target = 9

5
/ \
3   6
/ \   \
2   4   7

Target = 28

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.

Input:

5
/ \
3   6
/ \   \
2   4   7

Target = 9

Output: True

Input:

5
/ \
3   6
/ \   \
2   4   7

Target = 28

Output: False

```public class Program {

public static void Main(string[] args) {
var root = new TreeNode(1) {
left = new TreeNode(3) {
left = new TreeNode(5),
right = new TreeNode(7)
},
right = new TreeNode(9)
};

var res = FindTarget(root, 10);
Console.WriteLine(res);

}

public static bool FindTarget(TreeNode root, int k) {
var nums = new List<int>();
PreOrder(root, nums);
return TwoSum(nums.ToArray(), k);
}

public static void PreOrder(TreeNode root, List<int> nums) {
if(root == null) return;
PreOrder(root.left, nums);
PreOrder(root.right, nums);
}

public static bool TwoSum(int[] nums, int target) {
//用数组中的值做key，索引做value存下所有值
var dictionary = new Dictionary<int, int>();
for(int i = 0; i < nums.Length; i++) {
//记录差值
int complement = target - nums[i];
//若字典中已经存在这个值，说明匹配成功
if(dictionary.ContainsKey(complement)) return true;
//记录索引
dictionary[nums[i]] = i;
}
return false;
}

public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}

}```

`true`