# Question

Formatted question description: https://leetcode.ca/all/653.html

 653	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


# Algorithm

As long as it is the question of the sum of two numbers, you must remember to try to do it with HashSet.

This question is just to turn the array into a binary tree. We need to traverse the binary tree and use a HashSet. In the recursive function function,

• if node is empty, return false.
• If k minus the current node value exists in the HashSet, return true directly;
• otherwise, add the current node value to the HashSet, and then call the recursive function on the left and right sub-nodes and return together.

# Code

Java

Java

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
Set<Integer> set = new HashSet<Integer>();

public boolean findTarget(TreeNode root, int k) {
prePost(root);
for (int key : set) {
if (set.contains(k - key) && k - key != key)
return true;
}
return false;
}

public void prePost(TreeNode root) {
if (root == null)
return;