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

---

Seen this question in a real interview before?   

Yes  

是2sum的变形，遍历的时候，用hashset记录出现的数值以及次数。

代码：

HashMap<Integer, Integer> map = new HashMap<>(); int target = 0; public boolean findTarget(TreeNode root, int k) { if(root == null) return false; target = k; return preOrder(root); } private boolean preOrder(TreeNode node) { if(node == null) return false; if(map.containsKey(target-node.val)) { if(node.val * 2 == target) { return map.get(node.val) > 1; } else { return true; } } put(node.val); return preOrder(node.left) || preOrder(node.right); } private void put(Integer value) { if(map.containsKey(value)) { map.put(value, map.get(value) +1); } else { map.put(value, 1); } }