Given the root of a Binary Search Tree and a target number k, return true if there exist two elements in the BST such that their sum is equal to the given target.
Examples
Input: root = [5,3,6,2,4,null,7], k = 9 Output: true
Input: root = [5,3,6,2,4,null,7], k = 28 Output: false
Input: root = [2,1,3], k = 4 Output: true
Input: root = [2,1,3], k = 1 Output: false
Input: root = [2,1,3], k = 3 Output: true
Constraints
The number of nodes in the tree is in the range [1, 104]. -104 <= Node.val <= 104 root is guaranteed to be a valid binary search tree. -105 <= k <= 105
Java Solution
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean findTarget(TreeNode root, int k) {
Set<Integer> set = new HashSet<>();
return helper(root, k, set);
}
private boolean helper(TreeNode root, int k, Set<Integer> set) {
if(root == null) return false;
if(set.contains(root.val)) return true;
set.add(k - root.val);
return helper(root.left, k, set) || helper(root.right, k, set);
}
}
