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
No.1
Input:
Target = 9
Output: True
No.2
Input:
Target = 28
Output: False
Code
1
2
3
4
5
6
|
public class {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
|
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
|
public boolean findTarget(TreeNode root, int k) {
List<Integer> list = new ArrayList<>();
inorder(list, root);
int left = 0;
int right = list.size() - 1;
while (left < right) {
if (list.get(left) + list.get(right) < k)
left++;
else if (list.get(left) + list.get(right) > k)
right--;
else
return true;
}
return false;
}
private void inorder(List<Integer> list, TreeNode root) {
if (root == null)
return;
inorder(list, root.left);
list.add(root.val);
inorder(list, root.right);
}
|
近期评论