import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
/**
* https://leetcode.com/articles/two-sum-iv/
*/
public class TwoSumIV {
/**
* å…ˆé历一é，生æˆä¸€ä¸ªé€’增åºåˆ—，å†ä»Žä¸¤ç«¯å¾€ä¸é—´æ£€æŸ¥
*/
public boolean findTarget(TreeNode root, int k) {
List 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 nums) {
if (root == null) return;
inorder(root.left, nums);
nums.add(root.val);
inorder(root.right, nums);
}
/**
* 更简å•ä¸€ç‚¹ï¼ŒéåŽ†æ ‘ï¼Œç”¨ä¸€ä¸ªhashset记录æ¯ä¸ªå…ƒç´
* 时间空间都是O(n)
*/
public boolean findTarget2(TreeNode root, int k) {
return visit(root, k, new HashSet<>());
}
private boolean visit(TreeNode root, int k, HashSet set) {
if (root == null) {
return false;
}
if (set.contains(k - root.val)) {
return true;
}
set.add(root.val);
return visit(root.left, k, set) || visit(root.right, k, set);
}
}