-
Notifications
You must be signed in to change notification settings - Fork 3
Expand file tree
/
Copy pathtwoSumIV.java
More file actions
121 lines (115 loc) · 4.01 KB
/
twoSumIV.java
File metadata and controls
121 lines (115 loc) · 4.01 KB
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
import java.util.*;
class TreeNode{
int val;
TreeNode left;
TreeNode right;
TreeNode(int x){
val = x;
}
}
public class twoSumIV {
public static void main(String[] args){
twoSumIV obj = new twoSumIV();
String tree = "4(2(1)(3))(6(5))";
TreeNode root = obj.str2tree(tree);
System.out.println(root.val);
System.out.println(obj.findTargetv1(root,5));
System.out.println(obj.findTargetv2(root,5));
}
/* Approach 1: DFS + HashSet Time: O(n), Space: O(n)
this method also works for non-BSTs. The idea is to use a hashset
to save all nodes'values in the tree. At the meantime, we check whether
the hashset contains current node's complement.
* */
private boolean findTargetv1(TreeNode root, int k){
HashSet<Integer> set = new HashSet<>();
return dfs(root, k, set);
}
private boolean dfs(TreeNode root, int target, HashSet<Integer> set){
if(root == null){
return false;
}
set.add(root.val);
boolean left = dfs(root.left, target, set);
boolean right = dfs(root.right, target, set);
return set.contains(target - root.val) || left || right;
}
/* Approach 2: two pointers Time: O(n), Space: O(n)
Take advantage of the property of BST.
Use a sorted array to save the values of the nodes in the BST by using an inorder traversal.
* */
private boolean findTargetv2(TreeNode root, int k){
List<Integer> nums = new ArrayList<>();
inorder(root, nums);
int lo = 0, hi = nums.size()-1;
while(lo < hi){
if(nums.get(lo) + nums.get(hi) == k){
return true;
}else if (nums.get(lo) + nums.get(hi) < k){
lo ++;
}else{
hi --;
}
}
return false;
}
private void inorder(TreeNode root, List<Integer> nums){
if (root == null) return;
inorder(root.left, nums);
nums.add(root.val);
inorder(root.right, nums);
}
/* Approach 3: bst iterator Time: O(n), Space: O(logn)
相当于approach 2 的follow up，如果面试官问能否保持时间的同时优化空间，提示可以把BST想像成一个sorted array。
回答可以用two pointers，实现两个BST iterator，一个从小到大，一个从大到小。用stack实现iterator。
* */
/* a helper function to construct a binary tree from string(lc 536)
这个helper function我经常用，这样构造tree的时候方便点
ie:
input: "4(2(3)(1))(6(5))"
output: 4
/ \
2 6
/ \ /
3 1 5
Use a treenode stack. When ')' appears, it means a substree is constructed.
Pop it and connect it to its parent node.
* */
private TreeNode str2tree(String s){
if(s == null || s.length() == 0){
return null;
}
Stack<TreeNode> stack = new Stack<>();
int i = 0;
boolean sign = true;
while(i < s.length()){
if(Character.isDigit(s.charAt(i))){
int num = 0;
while(i < s.length() && Character.isDigit(s.charAt(i))){
num = num * 10 + s.charAt(i) - '0';
i ++;
}
if (!sign){
num = 0 - num;
sign = true;
}
stack.push(new TreeNode(num));
}else{
if (s.charAt(i) == '-'){
sign = false;
}
if (s.charAt(i) == ')'){
TreeNode child = stack.pop();
TreeNode parent = stack.peek();
if (parent.left == null){
parent.left = child;
}else{
parent.right = child;
}
}
i ++;
}
}
return stack.peek();
}
}