题目
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
答案
方法1
in order traverse the BST and get a sorted list, then apply binary search
class Solution {
// Do in order traversal,
public boolean findTarget(TreeNode root, int k) {
List<Integer> list = new ArrayList<Integer>();
Stack<TreeNode> stk = new Stack<TreeNode>();
if(root == null) return false;
TreeNode curr = root;
// Push all the way left
while(curr != null) {
stk.push(curr);
curr = curr.left;
}
while(stk.size() != 0) {
TreeNode t = stk.pop();
list.add(t.val);
if(t.right != null) {
curr = t.right;
while(curr != null) {
stk.push(curr);
curr = curr.left;
}
}
}
int i = 0;
int[] nums = new int[list.size()];
for(int x:list) nums[i++] = x;
int[] arr = twoSum(nums, k);
return arr[0] != 0 || arr[1] != 0;
}
public int[] twoSum(int[] numbers, int target) {
for(int i = 0; i < numbers.length; i++) {
int first = numbers[i];
int second_index = Arrays.binarySearch(numbers, i + 1, numbers.length, target - first);
if(second_index >= 0) return new int[] {i + 1, second_index + 1};
}
return new int[]{0,0};
}
}
方法2
in order traverse the BST and get a sorted list, then apply two pointers method
class Solution {
// Do in order traversal,
public boolean findTarget(TreeNode root, int k) {
List<Integer> list = new ArrayList<Integer>();
Stack<TreeNode> stk = new Stack<TreeNode>();
if(root == null) return false;
TreeNode curr = root;
// Push all the way left
while(curr != null) {
stk.push(curr);
curr = curr.left;
}
while(stk.size() != 0) {
TreeNode t = stk.pop();
list.add(t.val);
if(t.right != null) {
curr = t.right;
while(curr != null) {
stk.push(curr);
curr = curr.left;
}
}
}
// Two pointer solve two sum
int left = 0, right = list.size() - 1;
while(left < right) {
int first = list.get(left);
int second = list.get(right);
if(first + second == k) return true;
else if (first + second < k) left++;
else right--;
}
return false;
}
}
方法3
in order traverse the BST and get a sorted list, then apply hash table method
No code !
方法4
Apply two pointer method using a BST iterator
class Solution {
// Do in order traversal,
public boolean findTarget(TreeNode root, int k) {
if(root == null) return false;
Stack<TreeNode> stkSorted = new Stack<TreeNode>();
Stack<TreeNode> stkReverseSorted = new Stack<TreeNode>();
pushToStack(stkSorted, root, true);
pushToStack(stkReverseSorted, root, false);
while(true) {
TreeNode first = stkSorted.peek();
TreeNode second = stkReverseSorted.peek();
if(first == second) break;
if(first.val + second.val == k) return true;
else if(first.val + second.val < k) next(stkSorted, true);
else next(stkReverseSorted, false);
}
return false;
}
public void pushToStack(Stack<TreeNode> stk, TreeNode root, boolean left) {
while(root != null) {
stk.push(root);
if(left) root = root.left;
else root = root.right;
}
}
public void next(Stack<TreeNode> stk, boolean left) {
TreeNode t = stk.pop();
if(left) pushToStack(stk, t.right, left);
else pushToStack(stk, t.left, left);
}
}
