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
| class Solution {
public boolean findTarget(TreeNode root, int k) {
List<Integer> sortedList = new ArrayList<>();
dfs(sortedList, root);
int left = 0, right = sortedList.size() - 1;
while (left < right) {
int currSum = sortedList.get(left) + sortedList.get(right);
if (currSum < k) {
left += 1;
} else if (currSum > k) {
right -= 1;
} else {
return true;
}
}
return false;
}
private void dfs(List<Integer> sortedList, TreeNode node) {
if (node == null) {
return;
}
dfs(sortedList, node.left);
sortedList.add(node.val);
dfs(sortedList, node.right);
}
}
|
DFS把元素取出来, two pointers即可.
时间复杂度: O(n)
空间复杂度: O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public boolean findTarget(TreeNode root, int k) {
return dfs(root, new HashSet<>(), k);
}
private boolean dfs(TreeNode node, Set<Integer> visited, int k) {
if (node == null) {
return false;
}
int target = k - node.val;
if (visited.contains(target)) {
return true;
}
visited.add(node.val);
if (dfs(node.left, visited, k) || dfs(node.right, visited, k)) {
return true;
}
return false;
}
}
|
用hashset的解法.
时间复杂度和空间复杂度不变.
