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
Solution 1: hashset + DFS, Time Complexity:O(n)
, Space Complexity:O(n)
Set<Integer> hashset = new HashSet<>();
public boolean findTarget(TreeNode root, int k) {
if (root == null) {
return false;
}
if (hashset.contains(k - root.val)) {
return true;
}
hashset.add(root.val);
return findTarget(root.left, k) || findTarget(root.right, k);
}
Solution 2: inorder traversal得到递增的array,two pointers. Time Complexity:O(n)
, Space Complexity:O(n)
public boolean findTarget(TreeNode root, int k) {
List<Integer> nums = new ArrayList<>();
inorder(root, nums);
for(int i = 0, j = nums.size()-1; i<j;){
if(nums.get(i) + nums.get(j) == k)return true;
if(nums.get(i) + nums.get(j) < k)i++;
else j--;
}
return false;
}
public void inorder(TreeNode root, List<Integer> nums){
if(root == null)return;
inorder(root.left, nums);
nums.add(root.val);
inorder(root.right, nums);
}
Solution 3: The idea is to use binary search method. For each node, we check ifk - node.val
exists in this BST.
Time Complexity:O(nlogn)
, Space Complexity:O(height)
.
public boolean findTarget(TreeNode root, int k) {
return dfs(root, root, k);
}
public boolean dfs(TreeNode root, TreeNode cur, int k){
if(cur == null)return false;
return search(root, cur, k - cur.val) || dfs(root, cur.left, k) || dfs(root, cur.right, k);
}
public boolean search(TreeNode root, TreeNode cur, int value){
if(root == null)return false;
return (root.val == value) && (root != cur)
|| (root.val < value) && search(root.right, cur, value)
|| (root.val > value) && search(root.left, cur, value);
}
.