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.
Example 1:
Input: root = [5,3,6,2,4,null,7], k = 9 Output: true Example 2:
Input: root = [5,3,6,2,4,null,7], k = 28 Output: false Example 3:
Input: root = [2,1,3], k = 4 Output: true Example 4:
Input: root = [2,1,3], k = 1 Output: false Example 5:
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
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Solution {
public bool FindTarget(TreeNode root, int k) {
var set = new HashSet<int>();
return Helper(root,set,k);
}
private bool Helper(TreeNode root, HashSet<int> set, int k){
if(root == null){
return false;
}
if(set.Contains(k-root.val)){
return true;
}
set.Add(root.val);
return Helper(root.left,set,k)||Helper(root.right,set,k);
}
}Time Complexity: O(n)
Space Complexity: O(n)
