-
-
Notifications
You must be signed in to change notification settings - Fork 27
Expand file tree
/
Copy pathTwo Sum IV - Input is a BST.java
More file actions
executable file
·50 lines (40 loc) · 856 Bytes
/
Two Sum IV - Input is a BST.java
File metadata and controls
executable file
·50 lines (40 loc) · 856 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
E
1533407180
tags: Tree
HashSet to store visited items. Same old 2 sum trick.
```
/*
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
*/
// hashmap, in-order traverse for smaller items, recursively
class Solution {
Set<Integer> set = new HashSet<>();
public boolean findTarget(TreeNode root, int k) {
if (root == null) return false;
if (findTarget(root.left, k)) return true;
if (set.contains(k - root.val)) return true;
set.add(root.val);
if (findTarget(root.right, k)) return true;
return false;
}
}
```