Question
Formatted question description: https://leetcode.ca/all/653.html
653 Two Sum IV - Input is a BST
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
Algorithm
As long as it is the question of the sum of two numbers, you must remember to try to do it with HashSet.
This question is just to turn the array into a binary tree. We need to traverse the binary tree and use a HashSet. In the recursive function function,
- if node is empty, return false.
- If k minus the current node value exists in the HashSet, return true directly;
- otherwise, add the current node value to the HashSet, and then call the recursive function on the left and right sub-nodes and return together.
Code
Java
public class Two_Sum_IV_Input_is_a_BST {
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
// https://leetcode.com/problems/two-sum-iv-input-is-a-bst/solution/
public class Solution_queue {
public boolean findTarget(TreeNode root, int k) {
Set<Integer> set = new HashSet<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
if (queue.peek() != null) {
TreeNode node = queue.remove();
if (set.contains(k - node.val))
return true;
set.add(node.val);
queue.add(node.right);
queue.add(node.left);
} else
queue.remove();
}
return false;
}
}
// time: O(N)
// space: O(N)
public class Solution_usingBST { // inorder traversal to get sorted list
public boolean findTarget(TreeNode root, int k) {
List< Integer > list = new ArrayList<>();
inorder(root, list);
int l = 0, r = list.size() - 1;
while (l < r) {
int sum = list.get(l) + list.get(r);
if (sum == k)
return true;
if (sum < k)
l++;
else
r--;
}
return false;
}
public void inorder(TreeNode root, List < Integer > list) {
if (root == null)
return;
inorder(root.left, list);
list.add(root.val);
inorder(root.right, list);
}
}
// time: O(N)
// space: O(N)
public class Solution {
public boolean findTarget(TreeNode root, int k) {
Set < Integer > set = new HashSet();
return find(root, k, set);
}
public boolean find(TreeNode root, int k, Set< Integer > set) {
if (root == null) {
return false;
}
if (set.contains(k - root.val)) {
return true;
}
set.add(root.val);
return find(root.left, k, set) || find(root.right, k, set);
}
}
}
Java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
Set<Integer> set = new HashSet<Integer>();
public boolean findTarget(TreeNode root, int k) {
prePost(root);
for (int key : set) {
if (set.contains(k - key) && k - key != key)
return true;
}
return false;
}
public void prePost(TreeNode root) {
if (root == null)
return;
set.add(root.val);
prePost(root.left);
prePost(root.right);
}
}