653 Two Sum
Given a binary search tree and a target number, rerturn true if there exist two elements in the BST such that their sum is equal to the given target.
Approach 1 HashSet
public class Solution {
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;
set.add(root.val);
return find(root.left, k, set) || find(root.right, k, set);
}
}
Approach 2 BFS and HashSet
public class Solution {
public boolean findTarget(TreeNode root, int k) {
Set < Integer > set = new HashSet();
Queue < TreeNode > queue = new LinkedList();
queue.add(root);
while (!queue.isEmpty()) {
if (queue.peek() != null) {
TreeNode node = queue.remove();
if (set.contains(k - node.val))
return true;
set.add(node.val);
queue.add(node.right);
queue.add(node.left);
} else
queue.remove();
}
return false;
}
}
