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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean findTarget(TreeNode root, int k) {
if (root == null)
return false;
List<Integer> arr = new ArrayList<Integer>();
toArr(root, arr);
int head = 0, tail = arr.size()-1;
while (head < tail) {
if (arr.get(head)+arr.get(tail) == k)
return true;
else if (arr.get(head)+arr.get(tail) < k) {
head ++;
}
else tail --;
}
return false;
} private void toArr(TreeNode node, List<Integer> arr) {
if (node == null)
return ;
toArr(node.left, arr);
arr.add(node.val);
toArr(node.right, arr);
} }