Problem
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
My Solution
class Solution {
Map<Integer, Integer> map = new HashMap();
boolean flag = false;
public void preOrder(TreeNode node, int k, int order) {
if (node != null) {
if (map.containsValue(k - visit(node))) {
flag = true;
return;
} else {
map.put(order, visit(node));
}
preOrder(node.left, k, 2 * order);
preOrder(node.right, k, 2 * order + 1);
}
}
public int visit(TreeNode node) {
return node.val;
}
public boolean findTarget(TreeNode root, int k) {
preOrder(root, k, 1);
return flag;
}
}
Great Solution
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);
}
}
